Có $N$ chiếc xe, được đánh số từ $0$ đến $N-1$, nằm trên một trục số. Bạn được cung cấp danh sách các vị trí $X[0], X[1], \ldots, X[N - 1]$ và tốc độ tiêu thụ nhiên liệu trên mỗi đơn vị quãng đường $C[0], C[1], \ldots, C[N - 1]$ của chúng, mỗi danh sách đều đã được sắp xếp theo thứ tự tăng dần. Tuy nhiên, bạn không biết xe nào tương ứng với vị trí nào hoặc tốc độ tiêu thụ nhiên liệu nào. Nhưng bạn biết rằng mỗi xe có đúng một vị trí và đúng một tốc độ tiêu thụ nhiên liệu.

Tương đương với việc tồn tại hai hoán vị $P$ và $Q$ có độ dài $N$ sao cho chiếc xe thứ $i$ nằm tại vị trí $X[P[i]]$ và có tốc độ tiêu thụ nhiên liệu $C[Q[i]]$.

Hoán vị có độ dài $N$ là gì? Trong bài toán này, một hoán vị $P$ có độ dài $N$ là một mảng có độ dài $N$ sao cho $0 \leq P[i] \leq N-1$ với mọi $0 \leq i \leq N-1$ và $P[i] \neq P[j]$ với mọi $0 \leq i < j \leq N-1$. Ví dụ, $[2,1,0]$ là một hoán vị có độ dài $3$, nhưng $[1,2,3]$ và $[2,0,2]$ không phải là các hoán vị có độ dài $3$.

Với một cách gán $(P, Q)$ cụ thể, chúng ta định nghĩa tổng chi phí nhiên liệu để tập hợp tất cả các xe tại một điểm $y$ là $\text{cost}(P, Q, y) = \sum_{i=0}^{N-1} \lvert X[P[i]] -y \rvert \times C[Q[i]]$.

Với một điểm nguyên $p$, định nghĩa chi phí nhiên liệu trong trường hợp xấu nhất tại điểm $p$ là tổng chi phí nhiên liệu lớn nhất trên tất cả các cách gán $(P, Q)$ có thể. Nghĩa là, định nghĩa $\text{worst}(p) = \max\limits_{P,Q} \text{cost}(P, Q, p)$.

Nhiệm vụ của bạn là xác định một điểm nguyên $p$ sao cho chi phí nhiên liệu trong trường hợp xấu nhất tại điểm $p$, $\text{worst}(p)$, là nhỏ nhất. Nếu có nhiều điểm $p$ đạt được cùng một giá trị nhỏ nhất của $\text{worst}(p)$, bạn có thể báo cáo bất kỳ điểm nào trong số đó.

Chi tiết cài đặt

Bạn cần cài đặt thủ tục sau:

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

• $N$: số lượng xe.
• $X$: một mảng có độ dài $N$ mô tả các vị trí của các xe đã được sắp xếp theo thứ tự tăng dần.
• $C$: một mảng có độ dài $N$ mô tả tốc độ tiêu thụ nhiên liệu của các xe đã được sắp xếp theo thứ tự tăng dần.
• Thủ tục này được gọi chính xác một lần cho mỗi bộ dữ liệu kiểm tra.
• Thủ tục này nên trả về một số nguyên $p$, là điểm mà tại đó chi phí nhiên liệu trong trường hợp xấu nhất để tập hợp tất cả các xe tại $p$ là nhỏ nhất trong số tất cả các điểm nguyên.

Giới hạn

• $1 \le N \le 10\;000\;000$.
• $-10^9 \le X[i] \le 10^9$, với mọi $0 \leq i \leq N - 1$.
• $\color{red}{0 \le C[i] \le 100}$, với mọi $0 \leq i \leq N - 1$.
• $X[i] \leq X[j]$, với mọi $0 \leq i < j \leq N - 1$.
• $C[i] \leq C[j]$, với mọi $0 \leq i < j \leq N - 1$.

Nhiệm vụ con

1. (10 điểm) $N \le 1000, \lvert X[i] \rvert \le 10^3$.
2. (23 điểm) $N \le 100\;000$.
3. (17 điểm) $N \le 1\;000\;000$.
4. (31 điểm) $C[i] \le 1$, với mọi $0 \leq i \leq N - 1$.
5. (19 điểm) Không có giới hạn bổ sung.

Ví dụ

Xét lời gọi sau:

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

Giả sử $p = 1$. Khi đó, có thể chứng minh rằng các cách gán $P = [0,1,2]$ và $Q = [2,1,0]$ mang lại chi phí nhiên liệu trong trường hợp xấu nhất. Nghĩa là, $\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$. Lưu ý rằng có thể có các cách gán khác của $P$ và $Q$ mang lại chi phí nhiên liệu trong trường hợp xấu nhất, chẳng hạn như $P = [2,1,0]$ và $Q = [2,1,0]$.

Người ta cũng có thể chứng minh rằng điểm nguyên $p = 1$ là điểm có giá trị $\text{worst}(p)$ nhỏ nhất có thể. Do đó, lời gọi này nên trả về 1.

Trình chấm mẫu

Dữ liệu vào:

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

Dữ liệu ra:

Một số nguyên đại diện cho giá trị trả về của car_gathering.