在數線上共有 $N$ 輛車，編號從 $0$ 到 $N-1$。給定它們的位置列表 $X[0], X[1], \ldots, X[N - 1]$ 以及每單位距離的燃料消耗率 $C[0], C[1], \ldots, C[N - 1]$，兩者皆已按遞增順序排序。然而，你並不知道哪輛車對應哪個位置，也不知道哪輛車對應哪個燃料消耗率。但已知每輛車都有恰好一個位置與恰好一個燃料消耗率。

等價地說，存在兩個長度為 $N$ 的排列 $P$ 與 $Q$，使得第 $i$ 輛車位於位置 $X[P[i]]$，且其燃料消耗率為 $C[Q[i]]$。

什麼是長度為 $N$ 的排列？ 在本題中，長度為 $N$ 的排列 $P$ 是一個長度為 $N$ 的陣列，滿足對於所有 $0 \leq i \leq N-1$ 皆有 $0 \leq P[i] \leq N-1$，且對於所有 $0 \leq i < j \leq N-1$ 皆有 $P[i] \neq P[j]$。例如，$[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$，該點在所有整數點中，其最壞情況燃料成本為最小。

資料範圍

• $1 \le N \le 10\;000\;000$
• $-10^9 \le X[i] \le 10^9$，對於所有 $0 \leq i \leq N - 1$
• $\color{red}{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 回傳值的整數。