#include "train.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
const ll INF = 4e18;
vll finishes, starts;
#define x first
#define y second
ll endsBef(ll time) {
return lower_bound(finishes.begin(), finishes.end(), time)-finishes.begin();
}
ll startBef(ll time) {
return lower_bound(starts.begin(), starts.end(), time) - starts.begin();
}
struct edge {
ll from,to,l,r,cost;
};
struct update {
pll now;
ll time;
ll node;
bool operator<(const update& u) const {
return time > u.time;
}
};
bool cmp(const edge &a, const edge &b) {
return a.l < b.l;
}
ll cost(pll cur, ll mealsBef, ll price) {
ll mealsToBuy = max(0ll,mealsBef - cur.y);
ll addCost = mealsToBuy * price;
return cur.x + addCost;
}
long long solve(int N, int M, int W, vi T, vi X, vi Y,
vi A, vi B, vi C, vi L,
vi R) {
finishes.resize(W); for (int i = 0; i<W; ++i) finishes[i] = R[i]; sort(finishes.begin(), finishes.end());
starts.resize(W); for (int i = 0; i<W; ++i) starts[i] = L[i]; sort(starts.begin(), starts.end());
vector<edge> edges(M);
vector<vector<pll>> upto(N);
vector<int> ind(N, 0);
upto[0].push_back({0,0});
for (int i = 0; i<M; ++i) {
edges[i] = {X[i], Y[i], A[i], B[i], C[i]};
}
sort(edges.begin(), edges.end(), cmp);
priority_queue<update, vector<update>> pq;
for (edge e : edges) {
while (!pq.empty() && pq.top().time <= e.l) {
pll now = pq.top().now;
ll u = pq.top().node;
pq.pop();
if (!upto[u].empty() && upto[u].back().x >= now.x) {
upto[u].clear();
}
if (upto[u].empty()) {
upto[u] = {now};
ind[u] = 0;
continue;
}
else if (upto[u].back().y < now.y) {
ll dif = T[u] * (now.y - upto[u].back().y);
if (upto[u].back().x + dif > now.x) {
upto[u].push_back(now);
}
}
else if (upto[u].back().y > now.y) {
return 0;
}
}
ll node = e.from, u = e.to, l = e.l, r = e.r;
if (upto[node].empty()) continue;
ll mealsBef = endsBef(l);
while (ind[node] < upto[node].size()-1) {
ll curCost = cost(upto[node][ind[node]], mealsBef, T[node]);
ll costAf = cost(upto[node][ind[node]+1], mealsBef, T[node]);
if (costAf < curCost) ++ind[node];
else break;
}
ll addCost = cost(upto[node][ind[node]], mealsBef, T[node]);
ll totCost = addCost + e.cost;
pll now = {totCost, startBef(r+1)};
pq.push({now, r, u});
}
ll ans = INF;
while (!pq.empty()) {
pll now = pq.top().now;
ll u = pq.top().node;
pq.pop();
if (u != N-1) continue;
ans = min(ans, cost(now, W, T[N-1]));
}
for (pll p : upto[N-1]) {
ans = min(ans, cost(p, W, T[N-1]));
}
if (ans == INF) return -1;
return ans;
}
