#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

#define ll long long
#define ld long double
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define ROF(i,r,l) for(int i=(r);i>=(l);i--)
int inf=1000000007;
ll infl=2000000000000000007;
ll mod=1000000007;
ll mod1=998244353;

const int N=1007;

vector<pair<ll,ll>>V[N];
ll DP[N][N];
ll S[N];
ll X;
int n,m;

void init(int L,int nn,vector<ll>T,vector<int>W,int XX,int mm,vector<int>SS)
{
	X=XX,m=mm;
	FOR(i,0,m-1) S[i]=SS[i];
	FOR(i,0,nn-1) 
	{
		if(W[i]>X)
		{
			V[0].pb({T[i],W[i]});
			n++;
		}
	}
	sort(all(V[0]));
	FOR(i,1,m-1)
	{
		ll mn=infl;
		ROF(j,n-1,0) 
		{
			mn=min(mn,V[i-1][j].st+(S[i]-S[i-1])*V[i-1][j].nd);
			V[i].pb({mn,V[i-1][j].nd});
		}
		sort(all(V[i]));
	}
	ROF(i,m-1,0)
	{
		FOR(j,0,n-1)
		{
			bool is=0;
			FOR(l,i+1,m-1)
			{
				if(j>0&&V[l][j-1].st>=V[i][j].st+(S[l]-S[i])*X)
				{
					DP[i][j]=DP[l][j-1];
					is=1;
					break;
				}
			}
			if(!is) DP[i][j]=V[i][j].st+(S[m-1]-S[i])*X;
			debug(i,j,V[i][j].st,V[i][j].nd,DP[i][j]);
		}
	}
    return;
}

ll arrival_time(ll Y)
{
	ll ans=Y+(S[m-1]-S[0])*X;
	FOR(j,0,n-1) if(Y>V[0][j].st) ans=max(ans,V[0][j].st+V[0][j].nd*(S[m-1]-S[0]));
	return ans;
	ROF(j,n-1,0)
	{
		if(Y>V[0][j].st) 
		{
			debug(j,V[0][j].st,V[0][j].nd);
			FOR(i,1,m-1)
			{
				if(V[i][j].st>=Y+(S[i]-S[0])*X) 
				{
					debug(i);
					return DP[i][j];
				}
			}
			break;
		}
	}
	return Y+(S[m-1]-S[0])*X;
}