#include <bits/stdc++.h>
#include "overtaking.h"
// #include "grader.cpp"
using namespace std;
typedef long long ll;
const int MXN = 1005;
int n, m, l;
vector<ll> T;
vector<int> W, S;
vector<vector<ll>> dp;
void init(int L, int N, vector<ll> tt, vector<int> ww, int xx, int M, vector<int> ss){
n = N, l = L, m = M;
ww.push_back(xx), tt.push_back(-1);
W = ww, T = tt, S = ss;
return;
}
ll arrival_time(ll Y){
T[n] = Y;
dp.resize(n + 1);
for (int i = 0; i <= n; i ++){
dp[i].resize(m);
dp[i][0] = T[i];
}
vector<pair<pair<ll, int>, int>> order;
for (int j = 1; j < m; j ++){
order.clear();
for (int i = 0; i <= n; i ++)
order.push_back({{dp[i][j - 1], W[i]}, i});
sort(order.begin(), order.end());
ll mx = 0;
for (auto [P, i] : order){
mx = max(mx, dp[i][j - 1] + 1ll * W[i] * (S[j] - S[j - 1]));
dp[i][j] = mx;
}
}
return dp[n][m - 1];
}
