#include<iostream>
#include<algorithm>
#include<vector>
//#include "overtaking.h"
using namespace std;
const int MAX_N=1e3+3;
struct line
{
long long m,c;
long long calc(long long x){return m*x+c;}
long double intersect(line l){return (long double)(c-l.c)/(l.m-m);}
};
vector<line>lines;
vector<int>s;
long long l,n,m,x;
long double nxtpoint[MAX_N];
int nxtid[MAX_N];
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
l=L;
n=N;
x=X;
m=M;
s=S;
vector<pair<int,int>>order;
for(int i=0;i<n;i++)
{
order.push_back({W[i],i});
}
sort(order.begin(),order.end());
for(int i=0;i<n;i++)
{
int id=order[i].second;
line l;
l.m=W[id];
l.c=T[id];
lines.push_back(l);
}
for(int i=0;i<n;i++)
{
line cur=lines[i];
nxtpoint[i]=-1;
for(int j=i+1;j<n;j++)
{
line l=lines[j];
auto curpoint=cur.intersect(l);
if(curpoint<=0)continue;
if(nxtpoint[i]==-1 or curpoint<=nxtpoint[i])
{
nxtpoint[i]=curpoint;
nxtid[i]=j;
}
}
}
}
long long arrival_time(long long Y)
{
line cur;
cur.m=x;
cur.c=Y;
int id,idd;
for(int jj=1;jj<s.size();jj++)
{
int prvloc=s[jj-1];
int loc=s[jj];
long double point=-1;
idd=0;
for(auto l:lines)
{
if(l.m>cur.m)
{
auto curpoint=cur.intersect(l);
if(curpoint>loc && (point==-1 or curpoint<=point))
{
point=curpoint;
id=idd;
}
}
idd++;
}
if(point>=loc or point==-1)
{
continue;
}
while(nxtpoint[id]!=-1 && nxtpoint[id]<=loc)
{
id=nxtid[id];
}
cur.c+=lines[id].calc(loc)-cur.calc(loc);
}
return lines[id].calc(l);
}
