#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(), v.end()
const int M = 1000;
ll pre[M][M],x;
vector<pair<ll,int>> v[M];
vector<int> s;
int m;
void init(int l, int n, vector<long long> T, vector<int> w, int X, int m1, vector<int> S)
{
x=X,m=m1,s=S;
for (int i=0;i<n;i++)
{
if (w[i]<=x) continue;
v[0].push_back({T[i],w[i]});
}
for (int i=0;i+1<m;i++)
{
sort(all(v[i]));
ll mx=0;
for (int j=0;j<v[i].size();j++)
{
ll t=v[i][j].first,w=v[i][j].second;
mx=max(mx,t+w*(s[i+1]-s[i])),v[i+1].push_back({mx,w});
pre[i][j+1]=mx;
}
}
return;
}
long long arrival_time(long long y)
{
for (int i=0;i+1<m;i++)
{
int id=lower_bound(all(v[i]),make_pair(y,0))-begin(v[i]);
y=max(pre[i][id],y+x*(s[i+1]-s[i]));
}
return y;
}
