#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
int n,m;
int x,l;
vector<int>v;
struct line{
long long m,b;
line(long long _m,long long _b){
m=_m,b=_b;
}
long long get(long long x){return m*x+b;}
friend bool operator<(line a,line b){return a.m>b.m;}
};
vector<line>hull;
bool check(line a,line b,line c){
double m1=a.m,b1=a.b,m2=b.m,b2=b.b,m3=c.m,b3=c.b;
return (b3-b1)/(m1-m3)<(b2-b1)/(m1-m2);
}
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
n=N,m=M,x=X,v=S,l=L;
vector<line>l;
for(int i=0;i<N;i++)l.push_back(line(W[i],T[i]));
sort(l.begin(),l.end());
for(auto x:l){
while(hull.size()>1&&check(hull[hull.size()-2],hull.back(),x))hull.pop_back();
hull.push_back(x);
}
for(auto x:hull)cerr<<x.m<<" "<<x.b<<"\n";
return;
}
long long arrival_time(long long Y)
{
int cur=0;
line bus=line(x,Y);
for(int i=0;i<m;i++){
while(cur<hull.size()-1&&hull[i].get(v[i])>=hull[i].get(v[i+1]))cur++;
if(cur>=n)continue;
long long val=hull[cur].get(v[i]);
if(val<=bus.get(v[i])){
long long dif=bus.get(v[i])-val;
bus.b-=dif;
cur++;
}
}
return bus.get(l);
}
