#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define LL node * 2
#define RR node * 2 + 1
#define ll long long
#define MAXN 300005
const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;
ll t[MAXN], w[MAXN], s[MAXN], m, n, x;
ll compute(){
vector<ll> curr(n, 0);
for (ll i = 0; i < n; i++) curr[i] = t[i];
for (ll i = 1; i < m; i++){
vector<ll> todo(n);
iota(todo.begin(), todo.end(), 0);
sort(todo.begin(), todo.end(), [&](ll a, ll b){
return make_pair(curr[a], w[a]) < make_pair(curr[b], w[b]);
});
ll dist = s[i] - s[i - 1];
ll mini = 0;
for (auto j : todo){
ll to = curr[j] + dist * w[j];
curr[j] = max(mini, to);
mini = max(mini, to);
}
}
return curr[n - 1];
}
void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
n = N;
m = M;
for (ll i = 0; i < m; i++) s[i] = S[i];
for (ll i = 0; i < n; i++) t[i] = T[i], w[i] = W[i];
n++;
w[n - 1] = X;
}
long long arrival_time(long long Y)
{
t[n - 1] = Y;
return compute();
}
/*
int main()
{
fileio();
int L, N, X, M, Q;
assert(5 == scanf("%d %d %d %d %d", &L, &N, &X, &M, &Q));
std::vector<long long> T(N);
for (int i = 0; i < N; i++)
assert(1 == scanf("%lld", &T[i]));
std::vector<int> W(N);
for (int i = 0; i < N; i++)
assert(1 == scanf("%d", &W[i]));
std::vector<int> S(M);
for (int i = 0; i < M; i++)
assert(1 == scanf("%d", &S[i]));
std::vector<long long> Y(Q);
for (int i = 0; i < Q; i++)
assert(1 == scanf("%lld", &Y[i]));
fclose(stdin);
init(L, N, T, W, X, M, S);
std::vector<long long> res(Q);
for (int i = 0; i < Q; i++)
res[i] = arrival_time(Y[i]);
for (int i = 0; i < Q; i++)
printf("%lld\n", res[i]);
fclose(stdout);
return 0;
}*/
