#include "overtaking.h"
#include "bits/stdc++.h"
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define si(a_) (ll)(a_.size())
#define all(a_) a_.begin(),a_.end()
#define here cerr<<"========================================\n"
#define dbg(X_) cerr<<#X_<<": "<<X_<<endl;
#define ceri(a_,l_,r_) {for(ll i_=l_;i_<=r_;i_++) cerr<<a_[i_]<<" ";cerr<<endl;}
using namespace std;
using ll = int;
using pll = pair<ll,ll>;
const ll maxn = 1005;
ll n,l,m;
ll st[maxn],w[maxn];
ll s[maxn];
ll e[maxn][maxn];
ll t[maxn][maxn];
ll id[maxn];
ll x;
ll curt[maxn];
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,l = L,m = M,x = X;
for(ll i = 1;i<=n;i++) st[i] = T[i-1];
for(ll i = 1;i<=n;i++) w[i] = W[i-1];
for(ll i = 1;i<=m;i++) s[i] = S[i-1];
for(ll i = 1;i<=n;i++) t[1][i] = st[i];
for(ll j = 2;j<=m;j++){
for(ll i = 1;i<=n;i++){
e[j][i] = t[j-1][i] + w[i]*(s[j]-s[j-1]);
}
for(ll i = 1;i<=n;i++) curt[i] = t[j-1][i];;
iota(id+1,id+1+n,1);
sort(id+1,id+1+n,[](ll x,ll y){
return curt[x]<curt[y];
});
for(ll ik = 1;ik<=n;ik++){
ll i = id[ik];
ll ig = id[ik-1];
t[j][i] = max(t[j][ig],e[j][i]);
}
}
n++;
return;
}
ll pmx[maxn];
long long arrival_time(long long Y)
{
st[n] = Y;
w[n] = x;
t[1][n] = st[n];
// here;
// dbg(Y);
for(ll j = 2;j<=m;j++){
for(ll i = 1;i<=n;i++){
e[j][i] = t[j-1][i] + w[i]*(s[j]-s[j-1]);
}
for(ll i = 1;i<=n;i++) curt[i] = t[j-1][i];;
iota(id+1,id+1+n,1);
sort(id+1,id+1+n,[](ll x,ll y){
return curt[x]<curt[y];
});
ll last = 0;
for(ll ik = 1;ik<=n;ik++){
ll i = id[ik];
ll ig = id[ik-1];
pmx[i] = max(pmx[ig],e[j][i]);
}
for(ll ik = 1;ik<=n;ik++){
ll i = id[ik];
ll ig = id[ik-1];
if(curt[i]!=curt[ig]) last = ig;
t[j][i] = max(pmx[last],e[j][i]);
}
// cerr<<w[n]*(s[j]-s[j-1])<<endl;
// ceri(e[j],1,n);
// ceri(t[j],1,n);
}
return t[m][n];
}
