#include "overtaking.h"
#include <bits/stdc++.h>
#define ll long long
#define inf INT_MAX
using namespace std;
vector<ll> s;
vector<pair<ll,ll>> p;
ll l,n,x,m;
vector<vector<pair<pair<ll,ll>,int>>> ps(1005);
vector<vector<ll>> start(1005);
vector<pair<pair<ll,ll>,int>> cur;
ll pos = 0;
pair<ll,ll> pref[1005][1005];
ll dp[1005][1005];
ll h[1005][1005];
ll f(int xx,int y,ll hh){
//cout<<"!"<<xx<<" "<<y<<" "<<hh<<"\n";
if( y == m-1 ) return dp[xx][y] = hh;
if( dp[xx][y] != 0 ) return dp[xx][y];
int foo = lower_bound(start[y+1].begin(),start[y+1].end(),hh) - start[y+1].begin();
int l = y+1,r = m;
int res = inf;
while( l <= r ){
int tm = (l+r)/2;
ll vh = hh+(s[tm-1]-s[y])*x;
int vm = lower_bound(start[tm].begin(),start[tm].end(),vh) - start[tm].begin();
//cout<<"? "<<tm<<" "<<vh<<" "<<vm<<" "<<foo<<"\n";
if( vm < foo ){
res = min(res,tm);
r = tm-1;
}
else{
l = tm+1;
}
}
//cout<<"res :"<<res<<"\n";
if( res == inf ){
return dp[xx][y] = hh+(s.back()-s[y])*x;
}
foo = upper_bound(start[res-1].begin(),start[res-1].end(),hh+(s[res-2]-s[y])*x-1) - start[res-1].begin();
//cout<<"foo :"<<hh+(s[res-2]-s[y])*x<<" "<<foo<<" "<<res<<"\n";
return dp[xx][y] = f(pref[res-2][foo].second,res-1,h[pref[res-2][foo].second][res-1]);
}
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
n = N;
for(int i = 0 ; i < n ; i++) p.push_back({T[i],W[i]});
for(auto u : S) s.push_back(u);
l = L;
x = X;
m = M;
for(int i = 0 ; i < n ; i++){
if( p[i].second >= x ){
h[cur.size()][0] = p[i].first;
cur.push_back({p[i],cur.size()});
}
}
//preprocessing
n = cur.size();
for(int i = 1 ; i < m ; i++){
sort(cur.begin(),cur.end());
ll mx = 0;
for(int j = 0 ; j < n ; j++){
start[i].push_back(cur[j].first.first);
if( cur[j].first.first+(s[i]-pos)*cur[j].first.second <= mx ){
ps[i].push_back({{cur[j].first.first,mx},cur[j].second});
cur[j].first.first = mx;
h[cur[j].second][i] = cur[j].first.first;
}
else{
ps[i].push_back({{cur[j].first.first,cur[j].first.first+(s[i]-pos)*cur[j].first.second},cur[j].second});
cur[j].first.first = cur[j].first.first+(s[i]-pos)*cur[j].first.second;
mx = cur[j].first.first;
h[cur[j].second][i] = cur[j].first.first;
}
}
pos = s[i];
}
for(int i = 0 ; i < n ; i++) {
start[m].push_back(cur[i].first.first);
}
for(int i = 1 ; i <= m ; i++) {
sort(ps[i].begin(),ps[i].end());
sort(start[i].begin(),start[i].end());
}
//~ cout<<"start\n";
//~ for(int i = 0 ; i <= m ; i++){
//~ for(auto u : start[i]) cout<<u<<" ";
//~ cout<<"\n";
//~ }
//prefmax
for(int i = 0 ; i < m ; i++){
pref[i][0] = {0,0};
for(int j = 1 ; j <= (int) ps[i+1].size() ; j++){
if( ps[i+1][j-1].first.second > pref[i][j-1].first ){
pref[i][j] = {ps[i+1][j-1].first.second,ps[i+1][j-1].second};
}
else pref[i][j] = pref[i][j-1];
//cout<<"pref "<<i<<" "<<j<<" "<<pref[i][j].first<<" "<<pref[i][j].second<<"\n";
}
}
//dp
memset(dp,0,sizeof(dp));
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < m ; j++){
f(i,j,h[i][j]);
//cout<<"dp "<<i<<" "<<j<<" "<<h[i][j]<<" "<<dp[i][j]<<"\n";
}
}
return;
}
long long arrival_time(long long Y)
{
ll y = Y,ans;
int foo = lower_bound(start[1].begin(),start[1].end(),y) - start[1].begin();
int l = 1,r = m;
int res = inf;
while( l <= r ){
int tm = (l+r)/2;
ll vh = y+s[tm-1]*x;
int vm = lower_bound(start[tm].begin(),start[tm].end(),vh) - start[tm].begin();
//cout<<tm<<" "<<vh<<" "<<vm<<" "<<foo<<"\n";
if( vm < foo ){
res = min(res,tm);
r = tm-1;
}
else{
l = tm+1;
}
}
if( res == inf ){
ans = Y+s.back()*x;
return ans;
}
foo = upper_bound(start[res-1].begin(),start[res-1].end(),y+s[res-2]*x-1) - start[res-1].begin();
//cout<<"! "<<res<<" "<<foo<<"\n";
return dp[pref[res-2][foo].second][res-1];
}
//~ 100 1 10 3 1
//~ 0
//~ 20
//~ 0 20 100
//~ 10
//~ 1000 1 20 6 1
//~ 0
//~ 100
//~ 0 1 2 3 4 5
//~ 210
//~ 10000 2 2 2 1
//~ 500 0
//~ 5 10
//~ 0 100
//~ 800
//~ 10000 2 10 2 2
//~ 0 100
//~ 100 100
//~ 0 100
//~ 10 101
//~ 6 4 10 4 2
//~ 20 10 40 0
//~ 5 20 20 30
//~ 0 1 3 6
//~ 0 50
