//ANMHLIJKTJIY!
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#include "overtaking.h"
#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define N 1010
#define M 1000010
using namespace std;
ll n,m,pn,len,s[N],arr[N][N],res[N][N],ord[N],curt;
pair<ll,ll> t[N];
vector<ll> allv[N];
bool cmp(ll x,ll y)
{
	return arr[x][curt]<arr[y][curt];
}
void init(int _l,int _n,vector<ll> _t,vector<int> _w,int _x,int _m,vector<int> _s)
{
	ll i,j,k;
	len=_l,n=_n,m=_m;
	for(i=0;i<m;i++)
	{
		s[i]=_s[i];
	}
	for(i=0;i<n;i++)
	{
		t[i].S=_t[i];
		t[i].F=_w[i];
	}
	pn=_x;
	sort(t,t+n);
	reverse(t,t+n);
	for(i=0;i<n;i++)
	{
		if(t[i].F<=pn)
		{
			n=i;
			break;
		}
	}
	for(i=0;i<n;i++)
	{
		arr[i][0]=t[i].S;
	}
	for(i=1;i<m;i++)
	{
		curt=i-1;
		for(j=0;j<n;j++)
		{
			ord[j]=j;
		}
		sort(ord,ord+n,cmp);
		ll mx=0;
		for(j=k=0;j<n;j++)
		{
			while(k<j&&arr[ord[k]][i-1]<arr[ord[j]][i-1])
			{
				mx=max(mx,arr[ord[k++]][i]);
			}
			arr[ord[j]][i]=max(arr[ord[j]][i-1]+t[ord[j]].F*(s[i]-s[i-1]),mx);
		}
	}
	for(i=0;i<m;i++)
	{
		for(j=0;j<n;j++)
		{
			allv[i].push_back(arr[j][i]);
		}
		sort(allv[i].begin(),allv[i].end());
	}
	for(i=m-1;i>=0;i--)
	{
		for(j=0;j<allv[i].size();j++)
		{
			if(j==0)
			{
				res[i][j]=allv[i][j]+(s[m-1]-s[i])*pn;
				continue;
			}
			ll l=i,r=m-1;
			while(l<r)
			{
				ll mid=(l+r)>>1;
				if(allv[mid][j-1]<allv[i][j]+(s[mid]-s[i])*pn)
				{
					l=mid+1;
				}
				else
				{
					r=mid;
				}
			}
			if(l==m-1)
			{
				res[i][j]=max(allv[m-1][j-1],allv[i][j]+(s[m-1]-s[i])*pn);
			}
			else
			{
				ll p=lower_bound(allv[l].begin(),allv[l].end(),allv[l][j-1])-allv[l].begin();
				res[i][j]=res[l][p];
			}
		}
	}
	return;
}
ll arrival_time(ll x)
{
	ll num=lower_bound(allv[0].begin(),allv[0].end(),x)-allv[0].begin(),l=0,r=m-1;
	if(num==0)
	{
		return x+s[m-1]*pn;
	}
	while(l<r)
	{
		ll mid=(l+r)>>1;
		if(allv[mid][num-1]<x+s[mid]*pn)
		{
			l=mid+1;
		}
		else
		{
			r=mid;
		}
	}
	if(l==m-1)
	{
		return max(allv[m-1][num-1],x+s[m-1]*pn);
	}
	ll p=lower_bound(allv[l].begin(),allv[l].end(),allv[l][num-1])-allv[l].begin();
	return res[l][p];
}