#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 1000;
struct Data {
long long prevT;
long long currE;
int id;
bool operator < (const Data &x) {
if(prevT != x.prevT) return prevT < x.prevT;
return currE < x.currE;
}
};
Data f[mxN][mxN];
int n, m, x;
int s[mxN];
void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S) {
n = N;
m = M;
x = X;
for(int i = 0; i < M; i ++) s[i] = S[i];
for(int i = 0; i < M; i ++) {
if(i == 0) {
for(int j = 0; j < N; j ++) f[i][j] = {0, T[j], j};
sort(f[i], f[i] + N);
continue ;
}
for(int j = 0; j < N; j ++) {
f[i][j].prevT = f[i - 1][j].currE;
f[i][j].currE = f[i - 1][j].currE + W[f[i - 1][j].id] * (S[i] - S[i - 1]);
f[i][j].id = f[i - 1][j].id;
}
sort(f[i], f[i] + N);
for(int j = 0; j < N; j ++) {
f[i][j].currE = max(f[i][j].currE, (j ? f[i][j - 1].currE : 0));
}
}
}
long long arrival_time(long long Y) {
Data a = {0, Y};
for(int i = 1; i < m; i ++) {
a = {a.currE, a.currE + x * (s[i] - s[i - 1])};
int low = 0, high = n - 1;
while(low <= high) {
int mid = (low + high) / 2;
if(f[i][mid].prevT < a.prevT || (f[i][mid].prevT == a.prevT && f[i][mid].currE <= a.currE)) {
low = mid + 1;
} else {
high = mid - 1;
}
}
a.currE = max(a.currE, (low ? f[i][low - 1].currE : 0));
}
return a.currE;
}
/*int main() {
cin.tie(0)->sync_with_stdio(0);
init(6, 4, {20, 10, 40, 0}, {5, 20, 20, 30}, 10, 4, {0, 1, 3, 6});
cout << arrival_time(50) << "\n";
return 0;
}*/
