#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
struct cell
{
long long int st,w,ind;
};
bool cmp(cell a1,cell a2)
{
return a1.w>a2.w;
}
struct ver
{
long long int a;
bool operator<(const ver&b)const
{
return a>b.a;
}
};
map<ver,long long int>ma[1005];
long long int dp[1005][1005],n,m,b[1005],x;
cell a[1005];
void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
n=N;
m=M;
x=X;
for(int i=1;i<=N;i++)
{
a[i].ind=i;
a[i].w=W[i-1];
a[i].st=T[i-1];
}
for(int i=1;i<=M;i++)
{
b[i]=S[i-1];
}
sort(a+1,a+N+1,cmp);
for(int i=1;i<=n;i++)
{
dp[i][1]=a[i].st;
}
ver val,d;
for(int j=2;j<=m;j++)
{
for(int i=1;i<=n;i++)
{
d.a=dp[i][j-1];
val.a=dp[i][j-1]+(b[j]-b[j-1])*a[i].w;
//cout<<dp[i][j-1]<<" ";
dp[i][j]=val.a;
if(ma[j].upper_bound(d)!=ma[j].end())
{
dp[i][j]=max(dp[i][j],ma[j].upper_bound(d)->second);
//cout<<" | "<<(ma[j].upper_bound(d)->first.a)<<" | ";
}
ma[j][d]=max(ma[j][d],dp[i][j]);
}
}
}
long long arrival_time(long long Y)
{
ver d;
for(int i=2;i<=m;i++)
{
d.a=Y;
Y=max(Y+(b[i]-b[i-1])*x,ma[i].upper_bound(d)->second);
}
return Y;
}
