يصي

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const int INF = 1e7;
const ll llINF = 1e14;
const int mxN = 1e6 + 9;
const int mxM = 1e5 + 9;
const int MOD = 1e9 + 7;
const double pi = acos (-1);

long long x[mxN], dp[2 * mxN], tmpDP[2 * mxN];

struct room {
    int y;

    room (int Y) {
        y = Y;
    }
};

void solve () {
    int n, m, k;
    cin >> n >> m >> k;

    for (int i = 1; i <= n; i++)
        cin >> x[i];

    vector <pair<int, int>> next[2 * k + 9];
    map <pair<int, int>, int> hashy;
    vector <room> rooms[n + 1];
    int counter = 0;

    while (k--) {
        int x1, y1;
        cin >> x1 >> y1;

        int x2, y2;
        cin >> x2 >> y2;

        int h;
        cin >> h;

        if (!hashy.count({x1, y1}))
            hashy[{x1, y1}] = counter++;

        if (!hashy.count({x2, y2}))
            hashy[{x2, y2}] = counter++;

        rooms[x1].pb (room(y1));
        rooms[x2].pb (room(y2));
        next[hashy[{x1, y1}]].pb ({hashy[{x2, y2}], h});
    }

    for (int i = 0; i < 2 * k + 9; i++)
        dp[i] = llINF;

    for (auto r: rooms[1]) {
        int id = hashy[{1, r.y}];
        dp[id] = (r.y - 1) * x[1];
    }

    for (int i = 1; i <= n; i++) {
        if (rooms[i].size() == 0)
            continue;

        sort (rooms[i].begin(), rooms[i].end(), [&] (room r1, room r2) {
            if (r1.y != r2.y)
                return r1.y < r2.y;

            return false;
        });

        for (int j = 1; j < (int) rooms[i].size(); j++) {
            int curY = rooms[i][j].y, curId = hashy[{i, curY}];
            int preY = rooms[i][j - 1].y, preId = hashy[{i, preY}];

            dp[curId] = min (dp[curId], dp[preId] + (curY - preY) * x[i]);
        }

        for (int j = (int) rooms[i].size() - 2; j >= 0; j--) {
            int curY = rooms[i][j].y, curId = hashy[{i, curY}];
            int preY = rooms[i][j + 1].y, preId = hashy[{i, preY}];

            dp[curId] = min (dp[curId], dp[preId] + (preY - curY) * x[i]);
        }

        for (auto r: rooms[i]) {
            int curId = hashy[{i, r.y}];
            for (auto r2: next[curId])
                dp[r2.F] = min (dp[r2.F], dp[curId] - r2.S);
        }
    }


    long long res = llINF;
    for (auto u: rooms[n]) {
        int id = hashy[{n, u.y}];
        res = min (res, dp[id] + (m - u.y) * x[n]);
    }

    if (res < llINF) {
        cout << res << "\n";
    } else puts ("NO ESCAPE");

    return;
}

int main () {
    int t = 1;
    cin >> t;

    //ios_base::sync_with_stdio (0);
    //cin.tie (0);

    //setIO ("billboard");
    //preCalc ();
    while (t--) {
        //initialize common variables

        //go solve
        solve ();
    }

    return 0;
}