수직선 위에 $0$부터 $N-1$까지 번호가 매겨진 $N$대의 자동차가 있다. 각 자동차의 위치 $X[0], X[1], \ldots, X[N - 1]$과 단위 거리당 연료 소비율 $C[0], C[1], \ldots, C[N - 1]$이 각각 오름차순으로 정렬된 리스트로 주어진다. 하지만 어떤 자동차가 어떤 위치에 있고 어떤 연료 소비율을 가지는지는 알 수 없다. 단, 각 자동차는 정확히 하나의 위치와 정확히 하나의 연료 소비율을 가진다는 사실은 알고 있다.

동일하게, $i$번째 자동차가 위치 $X[P[i]]$에 있고 연료 소비율 $C[Q[i]]$를 가지도록 하는 길이 $N$인 두 순열 $P$와 $Q$가 존재한다.

길이 $N$인 순열이란 무엇인가? 이 문제에서 길이 $N$인 순열 $P$는 $0 \leq i \leq N-1$인 모든 $i$에 대해 $0 \leq P[i] \leq N-1$을 만족하고, $0 \leq i < j \leq N-1$인 모든 $i, j$에 대해 $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$인 배열.
• 이 함수는 각 테스트 케이스마다 정확히 한 번 호출된다.
• 이 함수는 모든 정수 점 중에서 최악의 경우 연료 비용이 최소가 되는 정수 점 $p$를 반환해야 한다.

제한

• $1 \le N \le 10\;000\;000$.
• 모든 $0 \leq i \leq N - 1$에 대해 $-10^9 \le X[i] \le 10^9$.
• 모든 $0 \leq i \leq N - 1$에 대해 $0 \le C[i] \le 100$.
• 모든 $0 \leq i < j \leq N - 1$에 대해 $X[i] \leq X[j]$.
• 모든 $0 \leq i < j \leq N - 1$에 대해 $C[i] \leq C[j]$.

서브태스크

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점) 모든 $0 \leq i \leq N - 1$에 대해 $C[i] \le 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의 반환 값을 나타내는 정수.