#include "train.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll LINF = 1e18 + 36;
const int INF = 1e9 + 36;
template<class T>bool minimize(T& a, T b){
if(a > b){
a = b;
return true;
}
return false;
}
int n, m, w;
vector<int>t, x, y, a, b, c, l, r;
namespace sub1{
const int lim = 1e3 + 5;
ll d[lim][lim];
struct Data{
int u, t;
ll w;
Data(){}
Data(int _u, int _t, ll _w) : u(_u), t(_t), w(_w) {}
friend bool operator <(Data a, Data b){
return a.w > b.w;
}
};
vector<int>g[lim];
ll solve(){
for(int i = 0; i < m; i++){
g[x[i]].push_back(i);
}
priority_queue<Data>pq;
memset(d, 0x0f, sizeof(d));
pq.push(Data(0, 0, d[0][0] = 0));
while(!pq.empty()){
auto [u, time, dist] = pq.top();
pq.pop();
if(d[u][time] == dist){
for(int& i : g[u]){
if(a[i] >= time){
ll new_dist = dist + c[i];
for(int j = 0; j < w; j++){
if(time < l[j] && a[i] > r[j]){
new_dist += t[u];
}
}
if(minimize(d[y[i]][b[i]], new_dist)){
pq.push(Data(y[i], b[i], new_dist));
}
}
}
}
}
ll ans = LINF;
for(int time = 0; time < lim; time++){
ll cur = d[n - 1][time];
for(int i = 0; i < w; i++){
if(l[i] > time){
cur += t[n - 1];
}
}
minimize(ans, cur);
}
return ans == LINF ? -1 : ans;
}
}
namespace sub2{
struct Data{
bool f;
int t, i;
Data(){}
Data(bool _f, int _t, int _i) : f(_f), t(_t), i(_i) {}
friend bool operator <(Data a, Data b){
return a.t != b.t ? a.t < b.t : a.f < b.f;
}
};
ll solve(){
vector<Data>event;
for(int i = 0; i < m; i++){
event.push_back(Data(false, a[i], i));
event.push_back(Data(true, b[i], i));
}
sort(event.begin(), event.end());
vector<ll>ans(n, LINF), wait(n, LINF);
ans[0] = 0;
for(auto& [f, t, i] : event){
if(!f){
minimize(wait[y[i]], ans[x[i]] + c[i]);
}
else{
minimize(ans[y[i]], wait[y[i]]);
}
}
return ans[n - 1] == LINF ? -1 : ans[n - 1];
}
}
namespace sub34{
const int SIZE = 736;
const int lim = 1e5 + 36;
struct Train{
int l, r, u, v, cost, low_meal;
Train(){}
Train(int _l, int _r, int _u, int _v, int _cost) : l(_l), r(_r), u(_u), v(_v), cost(_cost), low_meal(-1) {}
};
struct Event{
bool type;
int time, id;
Event(){}
Event(bool _type, int _time, int _id) : type(_type), time(_time), id(_id) {}
friend bool operator <(Event& a, Event& b){
return a.time != b.time ? a.time < b.time : a.type < b.type;
}
};
struct SegmentTree{
vector<ll>st, lazy;
int n;
SegmentTree(){}
SegmentTree(int n){
st.assign((this->n = n) << 2 | 3, LINF);
lazy.assign(n << 2 | 3, 0);
}
void propagate(int id, ll x){
st[id] += x;
lazy[id] += x;
}
void push_down(int id){
propagate(id << 1, lazy[id]);
propagate(id << 1 | 1, lazy[id]);
lazy[id] = 0;
}
void update_range(int id, int l, int r, int u, int v, int x){
if(l > v || r < u){
return;
}
if(u <= l && v >= r){
propagate(id, x);
return;
}
int m = (l + r) >> 1;
push_down(id);
update_range(id << 1, l, m, u, v, x);
update_range(id << 1 | 1, m + 1, r, u, v, x);
st[id] = min(st[id << 1], st[id << 1 | 1]);
}
void update_range(int u, int v, int x){
update_range(1, 1, n, u, v, x);
}
void update_pos(int p, ll x){
int id = 1, l = 1, r = n;
while(l < r){
int m = (l + r) >> 1;
push_down(id);
id <<= 1;
if(m < p){
id |= 1;
l = m + 1;
}
else{
r = m;
}
}
st[id] = x;
while((id >>= 1) > 0){
st[id] = min(st[id << 1], st[id << 1 | 1]);
}
}
ll get_min_pref(int p){
if(p == n){
return st[1];
}
ll ans = LINF;
int id = 1, l = 1, r = n;
while(l < r){
int m = (l + r) >> 1;
push_down(id);
id <<= 1;
if(m <= p){
minimize(ans, st[id]);
id |= 1;
l = m + 1;
}
else{
r = m;
}
}
return ans;
}
};
struct FenwickTree{
int bit[lim];
FenwickTree(){
memset(bit, 0, sizeof(bit));
}
void update(int p){
for(p++; p < lim; p += p & -p){
bit[p]++;
}
}
int get(int p){
int ans = 0;
for(p++; p > 0; p -= p & -p){
ans += bit[p];
}
return ans;
}
};
FenwickTree fen_meal;
ll dp[lim];
ll solve(){
vector<Train>train(1, Train(-1, 0, 0, 0, 0));
for(int i = 0; i < m; i++){
train.push_back(Train(a[i], b[i], x[i], y[i], c[i]));
}
sort(train.begin(), train.end(), [&] (auto i, auto j){
return i.v != j.v ? i.v < j.v : i.r < j.r;
});
train.push_back(Train(INF, INF, n - 1, n - 1, 0));
m += 2;
vector<pair<int, int>>planet(n, make_pair(m, m - 1));
vector<Event>event;
for(int i = 0; i < m; i++){
if(i == 0 || train[i].v != train[i - 1].v){
planet[train[i].v].first = i;
}
if(i == m - 1 || train[i].v != train[i + 1].v){
planet[train[i].v].second = i;
}
event.push_back(Event(false, train[i].l, i));
}
vector<SegmentTree>st;
vector<int>heavy_planet;
for(int i = 0; i < n; i++){
int N = planet[i].second - planet[i].first + 1;
if(N > SIZE){
st.push_back(SegmentTree(N));
heavy_planet.push_back(i);
}
}
vector<pair<int, int>>meal(w);
for(int i = 0; i < w; i++){
meal[i] = make_pair(l[i], r[i]);
}
sort(meal.begin(), meal.end(), [&] (auto i, auto j){
return i.first > j.first;
});
for(int i = 0; i < w; i++){
event.push_back(Event(true, meal[i].second, i));
}
for(int i = 0; i < m; i++){
int low = 0, high = w - 1;
while(low <= high){
int mid = (low + high) >> 1;
if(meal[mid].first > train[i].r){
low = (train[i].low_meal = mid) + 1;
}
else{
high = mid - 1;
}
}
}
sort(event.begin(), event.end());
memset(dp, 0x0f, sizeof(dp));
dp[0] = 0;
if(!heavy_planet.empty() && heavy_planet[0] == 0){
st[0].update_pos(1, 0);
}
for(auto& [type, time, id] : event){
if(type){
fen_meal.update(id);
for(int i = 0; i < heavy_planet.size(); i++){
int vertex = heavy_planet[i], low = planet[vertex].first, high = planet[vertex].second, p = low - 1;
while(low <= high){
int mid = (low + high) >> 1;
if(train[mid].r < meal[id].first){
low = (p = mid) + 1;
}
else{
high = mid - 1;
}
}
st[i].update_range(1, p + 1 - planet[vertex].first, t[vertex]);
}
}
else if(id > 0){
int p = lower_bound(heavy_planet.begin(), heavy_planet.end(), train[id].u) - heavy_planet.begin();
if(p < heavy_planet.size() && heavy_planet[p] == train[id].u){
int low = planet[train[id].u].first, high = planet[train[id].u].second, pos = low - 1;
while(low <= high){
int mid = (low + high) >> 1;
if(train[mid].r <= train[id].l){
low = (pos = mid) + 1;
}
else{
high = mid - 1;
}
}
dp[id] = st[p].get_min_pref(pos - planet[train[id].u].first + 1) + train[id].cost;
}
else{
for(int s = train[id].u, i = planet[s].first; i <= planet[s].second; i++){
if(train[i].r > train[id].l){
break;
}
minimize(dp[id], dp[i] + ll(t[s]) * fen_meal.get(train[i].low_meal) + train[id].cost);
}
}
if((p = lower_bound(heavy_planet.begin(), heavy_planet.end(), train[id].v) - heavy_planet.begin()) < heavy_planet.size() && heavy_planet[p] == train[id].v){
st[p].update_pos(id - planet[train[id].v].first + 1, dp[id]);
}
}
}
return dp[m - 1] >= LINF ? -1 : dp[m - 1];
}
}
ll solve(int N, int M, int W, vector<int>T, vector<int>X, vector<int>Y, vector<int>A, vector<int>B, vector<int>C, vector<int>L, vector<int>R){
n = N;
m = M;
swap(t, T);
swap(x, X);
swap(y, Y);
swap(a, A);
swap(b, B);
swap(c, C);
swap(l, L);
swap(r, R);
if((w = W) == 0){
return sub2::solve();
}
if(w <= 10 && max({n, m, *max_element(a.begin(), a.end()), *max_element(b.begin(), b.end()), *max_element(l.begin(), l.end()), *max_element(r.begin(), r.end())}) <= 1000){
return sub1::solve();
}
return sub34::solve();
}
