#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
long long haha[1001][1001];
vector<pair<long long,long long>> dp[1001];
vector<long long> w(0);
long long n,m,x;
vector<long long> s(0);
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;
vector<pair<long long, long long>> wow(0);
for(int i = 0; i < n; i++) {
wow.push_back({W[i],t[i]});
}
long long l,r;
for(int i = 0; i < n; i++) {
w.push_back(wow[i].first);
}
for(int i = 0; i < m; i++) {
s.push_back(S[i]);
}
for(long long i = 0; i < n; i++) {
haha[0][i] = wow[i].second;
}
for(long long i = 1; i < m; i++) {
for(long long j = 0; j < n; j++) {
haha[i][j] = haha[i-1][j]+(s[i]-s[i-1])*w[j];
}
vector<pair<long long,long long>> wut(0);
for(int j = 0; j < n; j++) {
wut.push_back({haha[i-1][j],haha[i][j]});
}
sort(wut.begin(),wut.end());
for(int j = 1; j < n; j++) {
wut[j] = {wut[j].first,max(wut[j].second,wut[j-1].second)};
}
for(long long j = 0; j < n; j++) {
dp[i].push_back(wut[j]);
if(haha[i-1][j] > wut[0].first) {
l = 0;
r = n-1;
while(l < r) {
int mid = (l+r+1)/2;
if(wut[mid].first < haha[i-1][j]) {
l = mid;
}
else {
r = mid-1;
}
}
haha[i][j] = max(haha[i][j],wut[l].second);
}
}
}
return;
}
long long arrival_time(long long y)
{
vector<long long> ans(m);
ans[0] = y;
long long l,r;
for(long long i = 1; i < m; i++) {
ans[i] = ans[i-1]+(s[i]-s[i-1])*x;
l = 0;
r = n-1;
if(ans[i-1] > dp[i][0].first) {
while(l < r) {
int mid = (l+r+1)/2;
if(dp[i][mid].first < ans[i-1]) {
l = mid;
}
else {
r = mid-1;
}
}
ans[i] = max(ans[i],dp[i][l].second);
}
}
return ans[m-1];
}
