数轴上有 $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$
• $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 返回值的整数。