#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 LL_INF = 5e18;
const int INT_INF = 2e9;
struct Train {
int x, y, a, b, c;
bool operator<(const Train& other) const {
return a < other.a;
}
};
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, LL_INF); vll min_val(N, LL_INF); min_val[0] = 0;
priority_queue<pint> min_updates;
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]);
int next_start = i == M-1 ? INT_INF : trains[i+1].a;
min_updates.push({trains[i].b, i});
while (!min_updates.empty() && min_updates.top().fi <= next_start) {
int ti = min_updates.top().se; min_updates.pop();
min_val[trains[ti].y] = min(min_val[trains[ti].y], dp[ti] - T[trains[ti].y]*meals_ended(trains[ti].b+1));
}
}
if (min_val[N-1] == LL_INF) return -1;
ll res = T[N-1]*W + min_val[N-1];
return res;
}
