#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
#define ll long long int
const int N = 2000;
ll dp[N][N];
int n, m;
vi W, S;
vector<ll> T;
void init(int L, int nn, std::vector<long long> TT, std::vector<int> WW, int X, int mm, std::vector<int> SS)
{
S = SS;
W = WW;
T = TT;
n = nn;
m = mm;
W.pb(X);
return;
}
long long arrival_time(long long Y)
{
T.pb(Y);
for(int i = 0; i <= n; ++i) dp[0][i] = T[i];
for(int i = 1; i < m; ++i){
ll dif = S[i] - S[i - 1];
vector<pair<ll, int>> q;
for(int j = 0; j <= n; ++j) q.pb({dp[i-1][j], j});
sort(all(q));
ll last = 0ll, last2 = 0ll;
for(int j = 0; j <= n; ++j){
int p = q[j].ss;
dp[i][p] = max(last, dp[i - 1][p] + dif * W[p]);
last2 = max(last2, dp[i][p]);
if(j + 1 <= n && q[j+1].ff != q[j].ff) last=max(last,last2);
}
// for(int j = 0; j <= n; ++j){
// cerr << dp[i][j] << ' ';
// }
// cerr << '\n';
}
T.pop_back();
return dp[m-1][n];
}
