数直線上に $N$ 台の車があり、それぞれ $0$ から $N-1$ の番号が付けられています。各車の位置 $X[0], X[1], \ldots, X[N - 1]$ と、単位距離あたりの燃料消費率 $C[0], C[1], \ldots, C[N - 1]$ が与えられます。これらはそれぞれ昇順にソートされています。しかし、どの車がどの位置に対応し、どの燃料消費率に対応しているかは分かりません。ただし、各車はちょうど1つの位置とちょうど1つの燃料消費率を持つことが分かっています。

言い換えると、長さ $N$ の2つの順列 $P$ と $Q$ が存在し、$i$ 番目の車は位置 $X[P[i]]$ にあり、燃料消費率 $C[Q[i]]$ を持つことになります。

長さ $N$ の順列とは何か？ この問題において、長さ $N$ の順列 $P$ とは、すべての $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]$ を満たす長さ $N$ の配列のことです。例えば、$[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)$ とします。

あなたのタスクは、最悪ケースの燃料コスト $\text{worst}(p)$ を最小化するような整数点 $p$ を求めることです。$\text{worst}(p)$ の最小値を与える点 $p$ が複数存在する場合は、そのうちのいずれかを報告すればよいです。

実装の詳細

以下の関数を実装してください。

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

• $N$: 車の台数。
• $X$: 車の位置を表す長さ $N$ の配列（昇順にソート済み）。
• $C$: 車の燃料消費率を表す長さ $N$ の配列（昇順にソート済み）。
• この関数は各テストケースに対してちょうど1回呼び出されます。
• この関数は、すべての整数点の中で最悪ケースの燃料コストが最小となるような整数点 $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 = [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 の戻り値を表す整数。