#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_starts(W); rep(i, W) meal_starts[i] = L[i];
sort(all(meal_starts));
auto meals_started = [&](int t) {
return lower_bound(all(meal_starts), t) - meal_starts.begin();
};
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); vpint min_val(N, {-1, 0});
priority_queue<pint, vpint, greater<>> min_updates;
rep(i, M) {
if (trains[i].x == 0) {
int m_end = meals_ended(trains[i].a);
dp[i] = trains[i].c + (ll)T[trains[i].x] * m_end;
}
if (min_val[trains[i].x].fi != -1) {
int m_start = meals_started(trains[i].a), m_end = meals_ended(trains[i].a), m_tot = m_start + m_end;
int min_idx = min_val[trains[i].x].fi, min_tot = min_val[trains[i].x].se;
dp[i] = trains[i].c + (ll)T[trains[i].x] * (m_tot - min_tot)/2 + dp[min_idx];
}
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();
if (dp[ti] != LL_INF) {
int m_start = meals_started(trains[ti].b+1), m_end = meals_ended(trains[ti].b+1), m_tot = m_start + m_end;
if (m_start > m_end) m_tot += 1;
int min_idx = min_val[trains[ti].y].fi, min_tot = min_val[trains[ti].y].se;
if (min_idx == -1) min_val[trains[ti].y] = {ti, m_tot};
else {
ll ov = dp[min_idx] - (ll)T[trains[ti].y] * (min_tot)/2, nv = dp[ti] - (ll)T[trains[ti].y] * (m_tot)/2;
if (ov > nv) min_val[trains[ti].y] = {ti, m_tot};
}
}
}
}
if (min_val[N-1].fi == -1) return -1;
int rmin_idx = min_val[N-1].fi, rmin_tot = min_val[N-1].se;
ll res = (ll)T[N-1] * (2*W - rmin_tot)/2 + dp[rmin_idx];
return res;
}
