#include <overtaking.h>
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long int
#define MOD (1000000000)+7;
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e3+100;
int L, n, m;
vector<int> W, S;
vector<ll> T;
void init(int l, int _n, vector<ll> t, vector<int> w, int x, int _m, vector<int> s){
W = w;
S = s;
T = t;
S = s;
n = _n;
m = _m;
W.pb(x);
}
ll dp[N][N];
ll arrival_time(ll Y){
T.pb(Y);
for(int i = 0; i <= n; ++i) dp[i][0] = T[i];
for(int j = 1; j < m; ++j){
// for(int i = 0; i <= n; ++i){
// cout << i << ' ' << j << ' ' << dp[i][j - 1] << '\n';
// }
// en;
vector<array<ll, 2>> b;
for(int i = 0; i <= n; ++i) b.pb({dp[i][j - 1], i});
sort(all(b));
ll cur = 0, curlast = 0;
for(int i = 0; i <= n; ++i){
int v = b[i][1];
// cout << v << ' ' << j << ' ' << dp[v][j - 1] << '\n';
if(i > 0 && dp[b[i - 1][1]][j - 1] < dp[v][j - 1]) curlast = cur;
cur = max(cur, dp[v][j - 1] + (ll)W[v] * (S[j] - S[j - 1]));
dp[v][j] = max(curlast, dp[v][j - 1] + (ll)W[v] * (S[j] - S[j - 1]));
}
}
T.pop_back();
return dp[n][m - 1];
}
