// In the name of Allah
#include <bits/stdc++.h>
#include "overtaking.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define F first
#define S second
#define endl '\n'
#define sep ' '
#define pb push_back
#define Mp make_pair
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
const int maxn = 1000 + 4;
const ll oo = 8e18 + 4;
int n, m; ll X;
pll A[maxn]; ll R[maxn]; int ind;
ll dp[maxn][maxn]; int arr[maxn];
pll dpx[maxn][maxn];
bool cmp(int i, int j) {
return (dp[ind][i] < dp[ind][j]);
}
void init(int L, int Nx, vector<ll> T, vector<int> W, int Z, int Mx, vector<int> S) {
n = Nx; m = Mx; X = Z;
for (int i = 0; i < n; i++) A[i] = Mp(T[i], W[i]);
for (int i = 0; i < m; i++) R[i] = S[i];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0) dp[i][j] = A[j].F;
else {
dp[i][j] = (dp[i - 1][j] + (R[i] - R[i - 1]) * A[j].S);
}
}
if (i - 1 >= 0) {
ind = i - 1;
iota(arr, arr + n, 0); sort(arr, arr + n, cmp);
ll x1 = -oo, x2 = -oo;
for (int r = 1; r < n; r++) {
int j1 = arr[r - 1], j2 = arr[r];
x2 = max(x2, dp[i][j1]);
if (dp[i - 1][j1] != dp[i - 1][j2]) x1 = x2;
dp[i][j2] = max(dp[i][j2], x1);
}
for (int j = 0; j < n; j++) {
dpx[i - 1][j] = Mp(dp[i - 1][j], dp[i][j]);
}
sort(dpx[i - 1], dpx[i - 1] + n);
for (int j = 1; j < n; j++) {
dpx[i - 1][j].S = max(dpx[i - 1][j].S, dpx[i - 1][j - 1].S);
}
}
}
return ;
}
ll arrival_time(ll Y) {
ll res = Y;
for (int i = 1; i < m; i++) {
ll resx = res + (R[i] - R[i - 1]) * X;
int r = lower_bound(dpx[i - 1], dpx[i - 1] + n, Mp(res, -oo)) - dpx[i - 1] - 1;
if (r >= 0) resx = max(resx, dpx[i - 1][r].S);
res = resx;
}
return res;
}
