#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 12;
int n,m,x;
vector<ll> t;
vector<int> w,s,ord[N];
ll e[N][N], dp[N][N];
void init(int L, int nn,vector<ll> T,vector<int> W, int X, int M,vector<int> S_) {
for(int i = 0; i < nn; i++) {
if(W[i] > X) {
n++;
t.push_back(T[i]);
w.push_back(W[i]);
}
}
s = S_;
m = M;
x = X;
if(!n) return;
for(int j = 0;j < m;j++) {
ord[j].resize(n);
iota(ord[j].begin(),ord[j].end(),0);
}
for(int j = 0;j < n;j++) {
e[0][j] = t[j];
}
sort(ord[0].begin(),ord[0].end(),[&](int x,int y) {
return make_pair(e[0][x],w[x]) < make_pair(e[0][y],w[y]);
});
for(int i = 1;i < M;i++) {
ll dist = s[i] - s[i - 1];
for(int j = 0;j < n;++j) {
int v = ord[i - 1][j];
e[i][v] = e[i - 1][v] + dist * 1ll * w[v];
if(j) {
int to = ord[i - 1][j - 1];
e[i][v] = max(e[i][v],e[i][to]);
}
}
sort(ord[i].begin(),ord[i].end(),[&](int x,int y){
return make_pair(e[i][x],w[x]) < make_pair(e[i][y],w[y]);
});
}
for(int i = 0; i < m; i++) {
sort(e[i], e[i] + n);
}
for(int i = m - 1; i >= 0; i--) {
dp[i][0] = e[i][0] + (s[m - 1] - s[i]) * 1ll * x;
for(int j = 1; j < n; j++) {
if(e[i][j] == e[i][j - 1]) {
dp[i][j] = dp[i][j - 1];
continue;
}
int l = i, r = m;
while(r - l > 1) {
int mid = (l + r) >> 1;
if(e[mid][j - 1] >= e[i][j] + (s[mid] - s[i]) * 1ll * x) {
r = mid;
} else {
l = mid;
}
}
if(r == m) {
dp[i][j] = e[i][j] + (s[m - 1] - s[i]) * 1ll * x;
} else {
dp[i][j] = dp[r][j - 1];
}
}
}
}
ll arrival_time(ll Y) {
ll cur = Y;
if(!n || Y <= e[0][0]) {
return Y + (s[m - 1] - s[0]) * 1ll * x;
}
auto find = [&]() {
int l = 0, r = n;
while(r - l > 1) {
int mid = (l + r) >> 1;
if(e[0][mid] >= Y) {
r = mid;
} else {
l = mid;
}
}
return l;
};
int k = find();
int l = 0, r = m ;
while(r - l > 1) {
int mid = (l + r) >> 1;
if(e[mid][k] >= (s[mid] - s[0]) * 1ll * x + Y) {
r = mid;
} else {
l = mid;
}
}
if(r == m) {
return Y + (s[m - 1] - s[0]) * 1ll * x;
}
return dp[r][k];
}
