#include "overtaking.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll l, n;
vector <ll> t;
vector <ll> w;
ll x, m;
vector <ll> s;
const int N = 1010;
ll tt[N][N];
vector <array <ll, 3>> v[N];
ll e[N][N];
ll prefmax[N][N];
void init(int L, int NN, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S){
l = L;
n = NN;
t = T;
x = X;
for(auto valor : W)
w.push_back(valor);
m = M;
for(auto valor : S)
s.push_back(valor);
for(int i = 0;i < n;i++){
tt[i][0] = t[i];
}
for(int j = 1;j < m;j++){
for(int i = 0;i < n;i++){
e[i][j] = tt[i][j-1] + (s[j]-s[j-1])*w[i];
v[j].push_back({tt[i][j-1], e[i][j], i});
}
sort(v[j].begin(), v[j].end());
ll res = 0;
for(auto [tmp, exp, i] : v[j]){
//cout << tmp << ' ' << exp << ' ' << i << '\n';
res = max(res, exp);
tt[i][j] = res;
}
//cout << '\n';
}
return;
}
bool comp(array <ll, 3> a, array <ll,3> b){
if(a[0] < b[0])
return true;
if(a[0] > b[0])
return false;
if(a[1] < b[1])
return true;
if(a[1] > b[1])
return false;
return (a[2] < b[2]);
}
long long arrival_time(long long Y){
tt[n][0] = Y;
for(int j = 1;j < m;j++){
int l = 0, r = n-1, ans = -1;
e[n][j] = tt[n][j-1] + (s[j]-s[j-1])*x;
array <ll, 3> aux = {tt[n][j-1], e[n][j], n};
//cout << tt[n][j-1] << ' ' << e[n][j] << ' ' << n << '\n';
while(l <= r){
int mid = (l+r)/2;
if(comp(aux, v[j][mid])){
r = mid-1;
}
else{
//cout << mid << '\n';
ans = mid;
l = mid+1;
}
}
/*for(auto [a, b, c] : v[j]){
cout << a << ' ' << b << ' ' << c << '\n';
}
cout << ans << ' ';*/
tt[n][j] = max(e[n][j], (ans == -1 ? 0 : tt[v[j][ans][2]][j]));
/*cout << tt[n][j] << '\n';
cout << '\n';*/
}
return tt[n][m-1];
}
