#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vint = vector<int>;
using vll = vector<ll>;
using pint = pair<int, int>;
using vpint = vector<pint>;
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a)-1; i >= (b); i--)
const ll INF = 5e18;
struct Train {
int x, y, a, b, c;
bool operator<(const Train& other) const {
return b < other.b;
}
};
ll solve(int N, int M, int W, vint T, vint X, vint Y, vint A, vint B, vint C, vint L, vint R) {
vector<Train> trains(M); rep(i, M) trains[i] = {X[i], Y[i], A[i], B[i], C[i]};
sort(all(trains));
vll dp(M, INF);
rep(i, M) {
if (trains[i].x == 0) {
int meal_count = 0;
rep(k, W) if (R[k] < trains[i].a) meal_count++;
dp[i] = min(dp[i], trains[i].c + (ll)T[trains[i].x]*meal_count);
} else {
rep(j, i) if (dp[j] != INF && trains[j].y == trains[i].x && trains[j].b <= trains[i].a) {
int meal_count = 0;
rep(k, W) if (trains[j].b < L[k] && R[k] < trains[i].a) meal_count++;
dp[i] = min(dp[i], trains[i].c + dp[j] + (ll)T[trains[i].x]*meal_count);
}
}
}
ll res = INF;
rep(i, M) if (trains[i].y == N-1) {
int meal_count = 0;
rep(k, W) if (trains[i].b < L[k]) meal_count++;
res = min(res, dp[i] + (ll)meal_count*T[N-1]);
}
if (res == INF) return -1;
return res;
}
