#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));
vint meal_ends(W); rep(i, W) meal_ends[i] = R[i];
sort(all(meal_ends));
auto meals_ended = [&](int t) {
return lower_bound(all(meal_ends), t) - meal_ends.begin();
};
vll dp(M, INF); vll min_val(N, INF); min_val[0] = 0;
rep(i, M) {
dp[i] = min(dp[i], trains[i].c + T[trains[i].x]*meals_ended(trains[i].a) + min_val[trains[i].x]);
min_val[trains[i].y] = min(min_val[trains[i].y], dp[i] - T[trains[i].y]*meals_ended(trains[i].b+1));
}
ll res = T[N-1]*W + min_val[N-1];
return res;
}
