Na osi liczbowej znajduje się $N$ samochodów, ponumerowanych od $0$ do $N-1$. Dane są listy ich pozycji $X[0], X[1], \ldots, X[N - 1]$ oraz wskaźniki zużycia paliwa na jednostkę odległości $C[0], C[1], \ldots, C[N - 1]$, obie posortowane w porządku rosnącym. Nie wiadomo jednak, który samochód odpowiada której pozycji ani któremu wskaźnikowi zużycia paliwa. Wiadomo jedynie, że każdy samochód ma dokładnie jedną pozycję i dokładnie jeden wskaźnik zużycia paliwa.

Równoważnie, istnieją dwie permutacje $P$ oraz $Q$ długości $N$ takie, że $i$-ty samochód znajduje się w pozycji $X[P[i]]$ i ma wskaźnik zużycia paliwa $C[Q[i]]$.

Czym jest permutacja długości $N$? W tym zadaniu permutacja $P$ długości $N$ to tablica długości $N$ taka, że $0 \leq P[i] \leq N-1$ dla wszystkich $0 \leq i \leq N-1$ oraz $P[i] \neq P[j]$ dla wszystkich $0 \leq i < j \leq N-1$. Na przykład $[2,1,0]$ jest permutacją długości $3$, ale $[1,2,3]$ oraz $[2,0,2]$ nie są permutacjami długości $3$.

Dla danego przypisania $(P, Q)$ definiujemy całkowity koszt paliwa potrzebny do zebrania wszystkich samochodów w punkcie $y$ jako $\text{cost}(P, Q, y) = \sum_{i=0}^{N-1} \lvert X[P[i]] -y \rvert \times C[Q[i]]$.

Dla danego punktu całkowitego $p$, definiujemy koszt paliwa w najgorszym przypadku w punkcie $p$ jako maksymalny całkowity koszt paliwa po wszystkich możliwych przypisaniach $(P, Q)$. Oznacza to, że $\text{worst}(p) = \max\limits_{P,Q} \text{cost}(P, Q, p)$.

Twoim zadaniem jest wyznaczenie punktu całkowitego $p$ takiego, że koszt paliwa w najgorszym przypadku w punkcie $p$, czyli $\text{worst}(p)$, jest zminimalizowany. Jeśli istnieje wiele punktów $p$, dla których osiągana jest ta sama minimalna wartość $\text{worst}(p)$, możesz zwrócić dowolny z nich.

Szczegóły implementacji

Należy zaimplementować następującą procedurę:

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

• $N$: liczba samochodów.
• $X$: tablica długości $N$ opisująca pozycje samochodów, posortowana w porządku rosnącym.
• $C$: tablica długości $N$ opisująca wskaźniki zużycia paliwa samochodów, posortowana w porządku rosnącym.
• Procedura ta jest wywoływana dokładnie raz dla każdego przypadku testowego.
• Procedura powinna zwrócić liczbę całkowitą $p$, dla której koszt paliwa w najgorszym przypadku zebrania wszystkich samochodów w punkcie $p$ jest zminimalizowany spośród wszystkich punktów całkowitych.

Ograniczenia

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

Podzadania

1. (10 punktów) $N \le 1000, \lvert X[i] \rvert \le 10^3$.
2. (23 punkty) $N \le 100\;000$.
3. (17 punktów) $N \le 1\;000\;000$.
4. (31 punktów) $C[i] \le 1$, dla wszystkich $0 \leq i \leq N - 1$.
5. (19 punktów) Brak dodatkowych ograniczeń.

Przykład

Rozważmy następujące wywołanie:

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

Załóżmy, że $p = 1$. Wtedy można udowodnić, że przypisania $P = [0,1,2]$ oraz $Q = [2,1,0]$ dają koszt paliwa w najgorszym przypadku. Oznacza to, że $\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$. Zauważ, że mogą istnieć inne przypisania $P$ i $Q$, które dają koszt paliwa w najgorszym przypadku, takie jak $P = [2,1,0]$ oraz $Q = [2,1,0]$.

Można również udowodnić, że punkt całkowity $p = 1$ jest punktem o minimalnej możliwej wartości $\text{worst}(p)$. Dlatego to wywołanie powinno zwrócić 1.

Wejście

Format wejścia:

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

Format wyjścia:

Liczba całkowita reprezentująca wartość zwracaną przez car_gathering.