#include "overtaking.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int l, n, m, x, y;
vector < long long > t;
vector < int > w, s;
int overtaking(int t0, int s0, int t1, int s1)
{
long long lt = 0, rt = l, mid, ans = l + 1;
while(lt <= rt)
{
mid = (lt + rt)/2;
long long time0 = t0 + s0 * mid;
long long time1 = t1 + s1 * mid;
if(time0 <= time1)
{
ans = mid;
rt = mid - 1;
}
else lt = mid + 1;
}
return ans;
}
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;
t = T;
x = X;
w = W;
m = M;
s = S;
return;
}
long long arrival_time(long long Y)
{
y = Y;
int t1 = t[0];
int s1 = w[0];
if(y <= t1 || (y >= t1 && s1 >= x))
{
long long ans = y + x * l;
return ans;
}
int inter = overtaking(x, y, s1, t1);
if(inter == l+1)
{
return y + l * x;
}
int lt = 0, rt = s.size()-1, mid, ans = l; /// pyrvoto po golqmo ot inter
while(lt <= rt)
{
mid = (lt + rt)/2;
if(inter <= s[mid])
{
ans = s[mid];
rt = mid - 1;
}
else lt = mid + 1;
}
long long time = y + inter * x + (l - ans) * x;
time += (ans - inter) * s1;
return time;
}
