#include "overtaking.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int A = 1e3+10;
ll l, n, x, m;
vector<ll> t, w, s;
ll arr[A][A], brr[A][A];
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
l = L;
n = N;
x = X;
m = M;
for(int i=0; i<n; i++){
ll a = T[i];
ll b = W[i];
t.push_back(a);
w.push_back(b);
}
for(int i=0; i<m; i++){
ll a = S[i];
s.push_back(a);
}
return;
}
long long arrival_time(long long Y)
{
for(int i=0; i<n+1; i++){
for(int j=0; j<m; j++){
arr[i][j] = 0;
brr[i][j] = 0;
}
}
for(int i=0; i<n; i++){
arr[i][0] = t[i];
//cout << arr[i][0] << " ";
}
//cout << 51 << endl;
arr[n][0] = Y;
for(int i=1; i<m; i++){
vector<tuple<ll, ll, ll>> v;
for(int j=0; j<n+1; j++){
if(j==n){
brr[j][i] = arr[j][i-1] + x*(s[i]-s[i-1]);
v.push_back({arr[j][i-1], brr[j][i], j});
} else {
brr[j][i] = arr[j][i-1] + w[j]*(s[i]-s[i-1]);
v.push_back({arr[j][i-1], brr[j][i], j});
}
}
sort(v.begin(), v.end());
tuple<ll, ll, ll> f = v[0];
ll curr = get<1>(f);
// for(int j = 0; j<n+1; j++){
// cout << brr[j][i] << " ";
// }
// cout << 67 << endl;
// for(int j = 0; j<n+1; j++){
// tuple<ll, ll, ll> temp = v[j];
// cout << get<0> (temp) << " " << get<1>(temp) << " " << get<2> (temp) << endl;
// }
// cout << 72 << endl;
for(int j=0; j<n+1; j++){
tuple<ll, ll, ll> temp = v[j];
ll aaa = get<2>(temp);
ll temp2 = get<1>(temp);
ll ans = max(curr, temp2);
curr = ans;
arr[aaa][i] = ans;
}
// for(int j = 0; j<n+1; j++){
// cout << arr[j][i] << " ";
// }
// cout << 84 << endl;
}
ll ans = arr[n][m-1];
return ans;
}
