#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
#define LOGN 20
const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;
struct SegTree{
vector<vector<ll>> tree;
vector<ll> compress;
ll n;
void add(ll node, ll l, ll r, ll sl, ll val){
tree[node].pb(-val);
if (l == r) return;
ll mid = (l + r) / 2;
if (sl <= mid) add(LL, l, mid, sl, val);
else add(RR, mid + 1, r, sl, val);
}
SegTree(vector<pii> arr){
n = arr.size();
sort(arr.begin(), arr.end());
for (auto i : arr) compress.pb(i.st);
unique(compress.begin(), compress.end());
sort(arr.begin(), arr.end(), [&](pii a, pii b){
return make_pair(-a.nd, a.st) < make_pair(-b.nd, b.st);
});
n = compress.size();
tree.resize(4 * n + 5);
for (auto i : arr){
ll pos = upper_bound(compress.begin(), compress.end(), i.st) - compress.begin();
pos--;
add(1, 0, n - 1, pos, i.nd);
}
}
ll query(ll node, ll l, ll r, ll sl, ll sr, ll val){
if (l > sr || r < sl) return 0;
if (l >= sl && r <= sr) {
return lower_bound(tree[node].begin(), tree[node].end(), -val) - tree[node].begin();
}
ll mid = (l + r) / 2;
return query(LL, l, mid, sl, sr, val) + query(RR, mid + 1, r, sl, sr, val);
}
ll query_good(ll pos, ll val){
ll l = 0, r = lower_bound(compress.begin(), compress.end(), pos) - compress.begin();
if (r == 0) return 0;
r--;
ll res = query(1, 0, n - 1, 0, r, val);
return res;
}
};
vector<SegTree*> trees;
vector<ll> ANS;
vector<vector<array<ll, 3>>> CURR;
vector<vector<ll>> TO;
ll s[MAXN], m;
map<ll, ll> dp[MAXN];
ll x;
ll compute(ll ind, ll pos){
if (ind == m - 1) return pos;
if (dp[ind].count(pos)) return dp[ind][pos];
ll ans = ind;
ll curr_cnt = trees[ind]->query_good(pos, x);
for (ll i = LOGN; i >= 0; i--){
ll to = ans + (1<<i);
if (to >= m) continue;
ll dist = s[to] - s[ind];
ll tmp_pos = pos + dist * x;
ll cnt = trees[to]->query_good(tmp_pos, x);
if (cnt == curr_cnt) ans = to;
}
ll dist = s[ans] - s[ind];
ll new_pos = pos + dist * x;
if (ans == m - 1) {
return dp[ind][pos] = new_pos;
}
ll poss = upper_bound(CURR[ans].begin(), CURR[ans].end(), array<ll, 3>({new_pos, x, INF})) - CURR[ans].begin();
poss--;
ll to = TO[ans][CURR[ans][poss][2]];
ll val = compute(ans + 1, to);
return dp[ind][pos] = val;
}
void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
x = X;
vector<ll> curr(N, 0);
ll n = N;
m = M;
for (ll i = 0; i < M; i++) s[i] = S[i];
for (ll i = 0; i < n; i++) curr[i] = T[i];
vector<pii> arr;
for (ll j = 0; j < N; j++) arr.pb({curr[j], W[j]});
vector<array<ll, 3>> tmp;
for (ll i = 0; i < n; i++) tmp.pb({curr[i], W[i], i});
sort(tmp.begin(), tmp.end());
CURR.pb(tmp);
SegTree *x = new SegTree(arr);
trees.pb(x);
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);
}
vector<pii> arr;
for (ll j = 0; j < N; j++) arr.pb({curr[j], W[j]});
SegTree *x = new SegTree(arr);
trees.pb(x);
vector<array<ll, 3>> tmp;
for (ll i = 0; i < n; i++) tmp.pb({curr[i], W[i], i});
sort(tmp.begin(), tmp.end());
CURR.pb(tmp);
vector<ll> too;
for (ll i = 0; i < n; i++) too.pb(curr[i]);
TO.pb(too);
}
}
long long arrival_time(long long Y)
{
return compute(0, Y);
}
/*
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;
}*/
