#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<pair<ll, ll>> car;
int n;
vector<vector<ll>> arr;
vector<ll> s;
int m;
ll x;
// true->fixed
// false +add
map<ll, pair<bool, ll> > seg;
map<ll, pair<bool, ll> > segtmp;
map<ll, pair<bool, ll> > segtmp2;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
for(int i = 0; i < N; ++i) {
if (X < W[i]) {
car.push_back({T[i], W[i]});
}
}
x = X;
n = car.size();
sort(car.begin(), car.end());
arr.push_back(vector<ll>{});
for (int j = 0; j < n; ++j) {
arr.back().push_back(car[j].first);
// std::cout<<car[j].first<<" ";
}
arr.back().push_back(2'100'000'000'000'000'000);
//std::cout<<std::endl;
m = M;
s.push_back(S[0]);
for (int i = 1; i < M; ++i) {
for(int j = 0; j < n; ++j) {
car[j].first += car[j].second * (S[i] - S[i - 1]);
}
for (int j = 1; j < n; ++j) {
car[j].first = max(car[j].first, car[j - 1].first);
}
sort(car.begin(), car.end());
arr.push_back(vector<ll>{});
for (int j = 0; j < n; ++j) {
arr.back().push_back(car[j].first);
// std::cout<<car[j].first<<" ";
}
arr.back().push_back(2'100'000'000'000'000'000);
//std::cout<<std::endl;
s.push_back(S[i]);
}
seg[1'000'000'000'000'000'000LL] = {false, 0};
for(int i = 1; i < m; ++i) {
segtmp.clear();
int j = -1;
ll b = seg.begin()->second.second;
for(auto& [key, value] : seg ) {
if (value.first) {
ll e = value.second;
while (arr[i - 1][j + 1] < e) {
++j;
}
if (j == -1) {
e += x * (s[i] - s[i - 1]);
} else {
e = max(e + x * (s[i] - s[i - 1]), arr[i][j]);
}
segtmp[key] = {true, e};
b = e + 1;
} else {
ll e = value.second + key;
while (arr[i - 1][j + 1] < b) {
++j;
}
if (j == -1) {
ll next = min(arr[i - 1][j + 1] - value.second, key);
segtmp[next] = {value.first, value.second + x * (s[i] - s[i - 1])};
b = value.second + next + 1;
if (next == key) continue;
++j;
}
while (arr[i - 1][j] < e) {
if (j >= 0) {
ll tar = arr[i][j] - x * (s[i] - s[i - 1]) - value.second;
if (b <= tar + value.second) {
segtmp[min(tar, key)] = {true, arr[i][j]};
b = min(tar, key) + value.second + 1;
}
ll next = min(arr[i - 1][j + 1], e) - value.second;
if (next + value.second >= b) {
segtmp[next] = {false, value.second + x * (s[i] - s[i - 1])};
b = next + value.second + 1;
}
} else {
ll next = min(arr[i - 1][j + 1], e) - value.second;
segtmp[next] = {false, value.second + x * (s[i] - s[i - 1])};
b = next + value.second + 1;
}
if (arr[i - 1][j + 1] < e) {
++j;
} else {
break;
}
}
b = e + 1;
}
}
swap(seg, segtmp);
//for(auto& [key, value] : seg) {
// cout<<key<<" "<<value.first<<" "<<value.second<<std::endl;
//}
//cout<<std::endl;
}
return;
}
long long arrival_time(long long Y)
{
auto it = seg.lower_bound(Y);
return it->second.first ? it->second.second : it->second.second + Y;
}
