#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n , tmp_cmp , m , x , len;
long long dp[N][N];
long long tim[N][N];
vector <int> w , ord[N] , s;
vector <long long> t;
bool cmp(int aa , int bb)
{
if(tim[aa][tmp_cmp] != tim[bb][tmp_cmp])
return tim[aa][tmp_cmp] < tim[bb][tmp_cmp];
return w[aa] < w[bb];
}
void Sort(int id)
{
tmp_cmp = id;
sort(ord[id].begin() , ord[id].end() , cmp);
}
long long Solve(long long val , int id)
{
if(id == m - 1)
return val;
int low = -1 , high = n;
while(high - low > 1)
{
int mid = (low + high) >> 1;
if(tim[ord[id][mid]][id] < val)
low = mid;
else
high = mid;
}
if(low == -1)
return val + 1LL * (len - s[id]) * x;
int l = id , r = m;
while(r - l > 1)
{
int mid = (l + r) >> 1;
if(tim[ord[mid][low]][mid] >= val + 1LL * x * (s[mid] - s[id]))
r = mid;
else
l = mid;
}
if(r == m)
return val + 1LL * (len - s[id]) * x;
return dp[ord[r][low]][r];
}
void init(int L, int nn, vector<long long> T, vector<int> W, int X, int mm, vector<int> S)
{
vector <int> tmp;
s = S;
m = mm;
x = X;
len = L;
for(int i = 0 ; i < nn ; i++) if(W[i] > X)
{
w.push_back(W[i]);
t.push_back(T[i]);
}
n = t.size();
for(int i = 0 ; i < n ; i++)
{
ord[0].push_back(i);
tim[i][0] = t[i];
}
Sort(0);
for(int j = 1 ; j < m ; j++)
{
for(int i = 0 ; i < n ; i++)
tim[i][j] = tim[i][j - 1] + 1LL * w[i] * (S[j] - S[j - 1]);
ord[j] = ord[j - 1];
for(int i = 1 ; i < n ; i++)
tim[ord[j][i]][j] = max(tim[ord[j][i]][j] , tim[ord[j][i - 1]][j]);
Sort(j);
}
for(int j = m - 1 ; j >= 0 ; j--)
{
for(int i = 0 ; i < n ; i++)
dp[i][j] = Solve(tim[i][j] , j);
}
return;
}
long long arrival_time(long long Y)
{
return Solve(Y , 0);
}
