#pragma GCC optimize("Ofast")
#include "train.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
namespace{
const ll mxN=4e5+5;
const ll inf=1e18;
struct segtree{
vector<vll> tree;
ll treelen;
void init(ll siz){
treelen=siz+1;
while(__builtin_popcount(treelen)!=1) treelen++;
tree=vector<vll> (2*treelen);
}
void add(ll idx, ll val){
ll tar=idx+treelen;
while(tar>0){
tree[tar].pb(val);
tar/=2;
}
}
void build(){
for(ll i=1;i<2*treelen;i++){
sort(tree[i].begin(), tree[i].end());
}
}
ll qry1(ll idx, ll low, ll high, ll qlow, ll qhigh, ll val){
if(low>=qlow && high<=qhigh){
ll tep=upper_bound(tree[idx].begin(), tree[idx].end(), val)-tree[idx].begin();
return (ll) tree[idx].size()-tep;
}
if(low>qhigh || high<qlow){
return 0LL;
}
ll mid=(low+high)/2;
return qry1(2*idx, low, mid, qlow, qhigh, val)+
qry1(2*idx+1, mid+1, high, qlow, qhigh, val);
}
ll qry(ll qlow, ll qhigh, ll val){
return qry1(1, 0, treelen-1, qlow, qhigh, val);
}
ll bs(ll idx, ll low, ll high, ll time1, ll time2, ll lef){
if(low==high){
ll cur=(ll) tree[idx].size()-(upper_bound(tree[idx].begin(), tree[idx].end(), time1)-tree[idx].begin());
ll cur2=(ll) tree[idx].size()-(upper_bound(tree[idx].begin(), tree[idx].end(), time2)-tree[idx].begin());
if(cur-cur2>=lef) return low;
else return inf;
}
ll mid=(low+high)/2;
ll cur=(ll) tree[2*idx].size()-(upper_bound(tree[2*idx].begin(), tree[2*idx].end(), time1)-tree[2*idx].begin());
ll cur2=(ll) tree[2*idx].size()-(upper_bound(tree[2*idx].begin(), tree[2*idx].end(), time2)-tree[2*idx].begin());
if(cur-cur2<lef){
lef-=cur-cur2;
return bs(2*idx+1, mid+1, high, time1, time2, lef);
}
else{
return bs(2*idx, low, mid, time1, time2, lef);
}
}
};
ll n, m, w;
vll t, x, y, a, b, c, l, r;
vll con;
vll in[mxN], out[mxN];
deque<ll> dq[mxN];
ll dp[mxN];
vector<pll> v;
segtree seg;
ll id(ll tar){
return lower_bound(con.begin(), con.end(), tar)-con.begin();
}
ll ceil_div(ll a, ll b){
return (a+b-1)/b;
}
ll f(ll idx, ll time){
if(dp[idx]==inf) return inf;
ll re=dp[idx];
ll tep=con.size()-1;
if(time!=inf){
tep=id(time);
if(tep==0) return re;
tep--;
}
// if(id(b[idx])+1>=(ll) con.size()) return re;
re+=t[y[idx]]*seg.qry(0, tep, b[idx]);
return re;
// ll lef=0, rig=w-1;
// ll f=-1;
// while(lef<=rig){
// ll mid=(lef+rig)/2;
// if(v[mid].F>b[idx]){
// f=mid;
// rig=mid-1;
// }
// else{
// lef=mid+1;
// }
// }
// if(f==-1) return re;
// ll s=-1;
// lef=0;
// rig=w-1;
// while(lef<=rig){
// ll mid=(lef+rig)/2;
// if(v[mid].S<time){
// s=mid;
// lef=mid+1;
// }
// else{
// rig=mid-1;
// }
// }
// if(s<f) return re;
// return re+t[y[idx]]*(s-f+1);
}
ll inter(ll idx1, ll idx2){
// ll lef=id(b[idx2]), rig=(ll) con.size()-1;
ll re=inf;
ll diff=dp[idx2]-dp[idx1];
if(dp[idx2]==inf && dp[idx1]==inf){
return b[idx2];
}
else if(dp[idx2]==inf){
return inf;
}
if(diff<=0) return b[idx2];
ll dumb=ceil_div(diff, t[y[idx1]]);
re=seg.bs(1, 0, seg.treelen-1, b[idx1], b[idx2], dumb);
if(re==inf) return inf;
if(re>=(ll) con.size()-1) return inf;
return max(con[re+1], b[idx2]);
}
}
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) {
con.clear();
n=N;
m=M;
w=W;
t=vll(n, 0);
for(ll i=0;i<n;i++){
t[i]=T[i];
}
x=vll(m+1, 0);
for(ll i=0;i<m;i++){
x[i]=X[i];
}
y=vll(m+1, 0);
for(ll i=0;i<m;i++){
y[i]=Y[i];
}
a=vll(m+1, 0);
for(ll i=0;i<m;i++){
a[i]=A[i];
con.pb(a[i]);
}
b=vll(m+1, 0);
for(ll i=0;i<m;i++){
b[i]=B[i];
con.pb(b[i]);
}
c=vll(m+1, 0);
for(ll i=0;i<m;i++){
c[i]=C[i];
}
l=vll(w, 0);
for(ll i=0;i<w;i++){
l[i]=L[i];
con.pb(l[i]);
}
r=vll(w, 0);
for(ll i=0;i<w;i++){
r[i]=R[i];
con.pb(r[i]);
}
// for(ll i=0;i<w;i++){
// v.pb({l[i], r[i]});
// }
sort(v.begin(), v.end());
con.pb(0);
sort(con.begin(), con.end());
con.erase(unique(con.begin(), con.end()), con.end());
seg.init((ll) con.size());
for(ll i=0;i<w;i++){
seg.add(id(r[i]), l[i]);
}
seg.build();
x[m]=0;
y[m]=0;
a[m]=0;
b[m]=0;
c[m]=0;
dp[m]=0;
for(ll i=0;i<m;i++){
in[id(a[i])].pb(i);
out[id(b[i])].pb(i);
}
dq[id(0)].pb(m);
for(ll i=0;i<(ll) con.size();i++){
for(auto &it:out[i]){
ll tar=y[it];
while((ll) dq[tar].size()>=2 && inter(dq[tar][(ll) dq[tar].size()-2], it)<=
inter(dq[tar][(ll) dq[tar].size()-2], dq[tar][(ll) dq[tar].size()-1])){
dq[tar].pop_back();
}
if(dq[tar].empty() || inter(dq[tar][(ll) dq[tar].size()-1], it)!=inf){
dq[tar].pb(it);
}
}
for(auto &it:in[i]){
ll tar=x[it];
if(dq[tar].empty()){
dp[it]=inf;
continue;
}
while((ll) dq[tar].size()>=2 && f(dq[tar][1], a[it])<=
f(dq[tar][0], a[it])){
dq[tar].pop_front();
}
dp[it]=f(dq[tar][0], a[it])+c[it];
}
}
ll ans=inf;
for(ll i=0;i<m;i++){
// cout<<i<<' '<<dp[i]<<'\n';
if(y[i]==n-1){
ans=min(ans, f(i, inf));
}
}
if(ans==inf) return -1;
return ans;
}
