#include "overtaking.h"
using namespace std;
typedef vector<int> vi;
typedef vector<long long> vl;
const int N = 1000, M = 1000;
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int n, m, a;
int aa[N]; long long bb[N]; int ii[N];
long long xx[M];
long long eval(int i, int x) {
return (long long) aa[i] * x + bb[i];
}
int compare_ba(int i, int j) {
return bb[i] != bb[j] ? (bb[i] < bb[j] ? -1 : 1) : aa[i] - aa[j];
}
int compare_a(int i, int j) {
return aa[i] - aa[j];
}
int (*compare)(int, int);
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = compare(ii[j], i_);
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
long long yy[M][N], dp[M][N];
int shoot(int h, int i, long long b) {
int lower = h, upper = m;
while (upper - lower > 1) {
h = (lower + upper) / 2;
if ((long long) a * xx[h] + b > yy[h][i])
lower = h;
else
upper = h;
}
return upper;
}
void init(int l, int n_, vl bb_, vi aa_, int a_, int m_, vi xx_) {
n = 0, m = m_, a = a_;
for (int i = 0; i < n_; i++)
if (aa_[i] > a_)
aa[n] = aa_[i], bb[n] = bb_[i], n++;
for (int h = 0; h < m; h++)
xx[h] = xx_[h];
for (int i = 0; i < n; i++)
ii[i] = i;
compare = compare_ba, sort(ii, 0, n);
for (int i = 0; i < n; i++)
yy[0][i] = bb[ii[i]];
for (int h = 1; h < m; h++) {
for (int i = 0, j; i < n; i = j) {
j = i + 1;
long long z = eval(ii[i], xx[h]);
while (j < n && eval(ii[j], xx[h]) <= z)
bb[ii[j]] = z - (long long) aa[ii[j]] * xx[h], j++;
compare = compare_a, sort(ii, i, j);
}
for (int i = 0; i < n; i++)
yy[h][i] = eval(ii[i], xx[h]);
}
for (int h = m - 1; h >= 0; h--)
for (int i = 0; i < n; i++)
if (i > 0 && yy[h][i] == yy[h][i - 1])
dp[h][i] = dp[h][i - 1];
else {
int h_ = i == 0 ? m : shoot(h, i - 1, yy[h][i] - (long long) a * xx[h]);
dp[h][i] = h_ == m ? (long long) a * (xx[m - 1] - xx[h]) + yy[h][i] : dp[h_][i - 1];
}
}
long long arrival_time(long long b) {
int lower = -1, upper = n;
while (upper - lower > 1) {
int i = (lower + upper) / 2;
if (yy[0][i] < b)
lower = i;
else
upper = i;
}
int i = lower, h_ = i == -1 ? m : shoot(0, i, b);
return h_ == m ? (long long) a * xx[m - 1] + b : dp[h_][i];
}
