#include <bits/stdc++.h>
#include "overtaking.h"
using namespace std;
using ll = long long;
const int N=1005;
const ll LIM=1e18;
int n,m,x;
ll s[N],dp[N][N];
vector<pair<int,ll>> bus;
vector<tuple<ll,ll,ll>> vals;
struct SegTree{
struct Node;
using Ptr = Node*;
struct Tag{
ll lz;
bool is_lz;
Tag():lz(0),is_lz(false){}
Tag(ll x):lz(x),is_lz(true){}
};
struct Node{
ll val;
Tag lz;
Ptr l,r;
Node(ll _val):val(_val),lz(),l(),r(){}
};
Ptr root;
ll offset;
SegTree():root(new Node(LIM)),offset(0){}
void apply(ll l,ll r,Ptr &t,Tag v){
if(!t)t=new Node(r);
if(v.is_lz){
t->val=v.lz;
t->lz=v;
}
}
void push(ll l,ll m,ll r,Ptr &t){
apply(l,m,t->l,t->lz);
apply(m+1,r,t->r,t->lz);
t->lz=Tag();
}
void pull(Ptr &t){
t->val=max(t->l->val,t->r->val);
}
void update(ll l,ll r,Ptr &t,ll x,ll y,const Tag &v){
if(y<l||r<x)return;
if(x<=l&&r<=y)return apply(l,r,t,v);
ll m=(l+r)/2;
push(l,m,r,t);
update(l,m,t->l,x,y,v);
update(m+1,r,t->r,x,y,v);
pull(t);
}
void update(ll x,ll y,ll v){
update(0,LIM,root,x,y,Tag(v-offset));
}
ll query(ll l,ll r,Ptr &t,ll x){
if(l==r)return t->val;
ll m=(l+r)/2;
if(x<=m){
if(!t->l)return t->lz.is_lz?t->lz.lz:x;
}else{
if(!t->r)return t->lz.is_lz?t->lz.lz:x;
}
push(l,m,r,t);
return x<=m?query(l,m,t->l,x):query(m+1,r,t->r,x);
}
ll query(ll x){
return query(0,LIM,root,x)+offset;
}
void add_all(ll x){
offset+=x;
}
template<class F>
ll find_first(ll l,ll r,Ptr &t,ll x,ll y,const F &f){
if(y<l||r<x||!f(t->val+offset))return LIM+1;
if(l==r)return l;
ll m=(l+r)/2;
push(l,m,r,t);
ll res=find_first(l,m,t->l,x,y,f);
if(res>LIM)res=find_first(m+1,r,t->r,x,y,f);
return res;
}
template<class F>
ll find_first(ll x,ll y,const F &f){
return find_first(0,LIM,root,x,y,f);
}
void dfs(ll l,ll r,Ptr t){
if(!t->l&&!t->r){
if(t->lz.is_lz)vals.emplace_back(l,r,t->val);
return;
}
ll m=(l+r)/2;
push(l,m,r,t);
dfs(l,m,t->l);
dfs(m+1,r,t->r);
}
void dfs(){
dfs(0,LIM,root);
}
}seg;
void init(int _l,int _n,vector<ll> _t,vector<int> _w,int _x,int _m,vector<int> _s){
n=_n,m=_m-1,x=_x;
for(int i=0;i<=m;i++)s[i]=_s[i];
for(int i=0;i<n;i++)bus.emplace_back(_w[i],_t[i]);
sort(bus.rbegin(),bus.rend());
while(!bus.empty()&&bus.back().first<=x)bus.pop_back();
n=bus.size();
for(int i=0;i<n;i++)dp[0][i]=bus[i].second;
for(int i=0;i<m;i++){
ll dist=s[i+1]-s[i];
vector<pair<ll,ll>> exp,real;
for(int j=0;j<n;j++){
ll w=bus[j].first;
dp[i+1][j]=dp[i][j]+w*dist;
exp.emplace_back(dp[i][j],dp[i+1][j]);
}
sort(exp.begin(),exp.end());
for(auto [l,r]:exp){
if(!real.empty()){
if(real.back().first==l)real.back().second=r;
else if(real.back().second<r)real.emplace_back(l,r);
}else{
real.emplace_back(l,r);
}
}
auto calc=[&](ll x){
auto it=lower_bound(real.begin(),real.end(),pair<ll,ll>(x,0));
if(it!=real.begin())return prev(it)->second;
return 0LL;
};
for(int j=0;j<n;j++){
dp[i+1][j]=max(dp[i+1][j],calc(dp[i][j]));
}
reverse(real.begin(),real.end());
vector<tuple<ll,ll,ll>> upd;
ll dif=x*dist;
ll last=LIM;
for(auto [l,r]:real){
ll l2=seg.find_first(0,last,[&](ll v){return v>l;});
if(l2>last)continue;
ll r2=min(seg.find_first(l2,last,[&](ll v){return v+dif>r;})-1,last);
upd.emplace_back(l2,r2,r);
last=l2-1;
}
seg.add_all(dif);
for(auto [l,r,v]:upd)seg.update(l,r,v);
}
seg.dfs();
}
ll arrival_time(ll y){
auto it=lower_bound(vals.begin(),vals.end(),make_tuple(y+1,0LL,0LL));
if(it==vals.begin())return y+seg.offset;
auto [l,r,v]=*prev(it);
return (y<=r?v:y)+seg.offset;
}
