На числовой прямой находится $N$ автомобилей, пронумерованных от $0$ до $N-1$. Вам даны списки их позиций $X[0], X[1], \ldots, X[N - 1]$ и их коэффициентов расхода топлива на единицу расстояния $C[0], C[1], \ldots, C[N - 1]$, каждый из которых отсортирован в порядке возрастания. Однако вы не знаете, какой автомобиль соответствует какой позиции или какому коэффициенту расхода топлива. Известно лишь, что у каждого автомобиля есть ровно одна позиция и ровно один коэффициент расхода топлива.

Эквивалентно, существуют две перестановки $P$ и $Q$ длины $N$ такие, что $i$-й автомобиль находится в позиции $X[P[i]]$ и имеет коэффициент расхода топлива $C[Q[i]]$.

Что такое перестановка длины $N$? В этой задаче перестановка $P$ длины $N$ — это массив длины $N$, такой что $0 \leq P[i] \leq N-1$ для всех $0 \leq i \leq N-1$ и $P[i] \neq P[j]$ для всех $0 \leq i < j \leq N-1$. Например, $[2,1,0]$ является перестановкой длины $3$, а $[1,2,3]$ и $[2,0,2]$ не являются перестановками длины $3$.

Для заданного распределения $(P, Q)$ определим общую стоимость топлива для сбора всех автомобилей в точке $y$ как $\text{cost}(P, Q, y) = \sum_{i=0}^{N-1} \lvert X[P[i]] -y \rvert \times C[Q[i]]$.

Для заданной целочисленной точки $p$ определим худшую стоимость топлива в точке $p$ как максимальную общую стоимость топлива по всем возможным распределениям $(P, Q)$. То есть, $\text{worst}(p) = \max\limits_{P,Q} \text{cost}(P, Q, p)$.

Ваша задача — определить такую целочисленную точку $p$, чтобы худшая стоимость топлива в точке $p$, $\text{worst}(p)$, была минимальной. Если существует несколько точек $p$, достигающих одного и того же минимального значения $\text{worst}(p)$, вы можете вернуть любую из них.

Детали реализации

Вам необходимо реализовать следующую функцию:

int car_gathering(int N, std::vector<int> X, std::vector<int> C)

• $N$: количество автомобилей.
• $X$: массив длины $N$, описывающий позиции автомобилей, отсортированный в порядке возрастания.
• $C$: массив длины $N$, описывающий коэффициенты расхода топлива автомобилей, отсортированный в порядке возрастания.
• Эта функция вызывается ровно один раз для каждого теста.
• Функция должна вернуть целое число $p$, для которого худшая стоимость топлива при сборе всех автомобилей в точке $p$ минимальна среди всех целочисленных точек.

Ограничения

• $1 \le N \le 10\;000\;000$.
• $-10^9 \le X[i] \le 10^9$ для всех $0 \leq i \leq N - 1$.
• $0 \le C[i] \le 100$ для всех $0 \leq i \leq N - 1$.
• $X[i] \leq X[j]$ для всех $0 \leq i < j \leq N - 1$.
• $C[i] \leq C[j]$ для всех $0 \leq i < j \leq N - 1$.

Подзадачи

1. (10 баллов) $N \le 1000, \lvert X[i] \rvert \le 10^3$.
2. (23 балла) $N \le 100\;000$.
3. (17 баллов) $N \le 1\;000\;000$.
4. (31 балл) $C[i] \le 1$ для всех $0 \leq i \leq N - 1$.
5. (19 баллов) Без дополнительных ограничений.

Примеры

Рассмотрим следующий вызов:

car_gathering(3, [-1, 2, 3], [1, 1, 2])

Предположим, $p = 1$. Тогда можно доказать, что распределения $P = [0,1,2]$ и $Q = [2,1,0]$ дают худшую стоимость топлива. То есть, $\text{worst}(p) = \text{cost}(P, Q, p) = (\lvert -1 - 1 \rvert \times 2) + (\lvert 2-1 \rvert \times 1) + (\lvert 3-1 \rvert \times 1) = 7$. Заметим, что могут существовать и другие распределения $P$ и $Q$, дающие худшую стоимость топлива, например $P = [2,1,0]$ и $Q = [2,1,0]$.

Также можно доказать, что целочисленная точка $p = 1$ является точкой с минимально возможным значением $\text{worst}(p)$. Поэтому данный вызов должен вернуть 1.

Примеры входных и выходных данных

Формат входных данных:

N
X[0] X[1] ... X[N - 1]
C[0] C[1] ... C[N - 1]

Формат выходных данных:

Целое число, представляющее возвращаемое значение функции car_gathering.