#include "overtaking.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
const long long INF = 1e17;
typedef long long ll;
const ll MOD = (ll)1e9+7;
#define P pair
#define F first
#define pb push_back
#define V vector
#define all(v) v.begin(), v.end()
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_multiset;
struct station {
ll t;
ll w;
};
bool sorted(station a,station b) {
if (a.t==b.t) {
return a.w<b.w;
}
return a.t<b.t;
}
station a[1001][1001],e[1001][1001];
ll s[1001];
int n,m;
ll x;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
x=X;
n=N,m=M;
for (int i=0;i<N;i++) {
a[0][i].t=T[i];
a[0][i].w=W[i];
}
for (int i=0;i<M;i++) {
s[i]=S[i];
}
sort(a[0],a[0]+N,sorted);
for (int i=0;i<M-1;i++) {
for (int j=0;j<N;j++) {
e[i+1][j].t=a[i][j].t+(S[i+1]-S[i])*a[i][j].w;
e[i+1][j].w=a[i][j].w;
}
ll maxd[N];
maxd[0]=e[i+1][0].t;
for (int j=1;j<N;j++) {
maxd[j]=max(maxd[j-1],e[i+1][j].t);
}
for (int j=0;j<N;j++) {
a[i+1][j].t=maxd[j];
a[i+1][j].w=a[i][j].w;
}
sort(a[i+1],a[i+1]+N,sorted);
}
}
long long arrival_time(long long Y)
{
ll ans=Y;
int curr=-1;
for (int i=0;i<n;i++) {
if (a[0][i].t<Y || (a[0][i].t==Y && a[0][i].w<x)) {
curr++;
}
}
for (int i=1;i<m;i++) {
ll b=((s[i]-s[i-1])*x)+ans;
if (curr!=-1) {
b=max(b,a[i][curr].t);
}
ans=b;
int l=0,r=curr;
int f=-1;
while (l<=r) {
int mid=l+(r-l)/2;
if (a[i][mid].t==b && a[i][mid].w>x) {
f=mid;
r=mid-1;
}
else
l=mid+1;
}
if (f!=-1) {
curr=f-1;
}
}
return ans;
}
