Hay $N$ coches, numerados del $0$ al $N-1$, en una recta numérica. Se proporcionan las listas de sus posiciones $X[0], X[1], \ldots, X[N - 1]$ y sus tasas de consumo de combustible por unidad $C[0], C[1], \ldots, C[N - 1]$, cada una ordenada de forma creciente. Sin embargo, no se sabe qué coche corresponde a qué posición o a qué tasa de consumo de combustible. Pero se sabe que cada coche tiene exactamente una posición y exactamente una tasa de consumo de combustible.

De manera equivalente, existen dos permutaciones $P$ y $Q$ de longitud $N$ tales que el $i$-ésimo coche está ubicado en la posición $X[P[i]]$ y tiene una tasa de consumo de combustible $C[Q[i]]$.

¿Qué es una permutación de longitud $N$? En este problema, una permutación $P$ de longitud $N$ es un arreglo de longitud $N$ tal que $0 \leq P[i] \leq N-1$ para todo $0 \leq i \leq N-1$ y $P[i] \neq P[j]$ para todo $0 \leq i < j \leq N-1$. Por ejemplo, $[2,1,0]$ es una permutación de longitud $3$, pero $[1,2,3]$ y $[2,0,2]$ no son permutaciones de longitud $3$.

Dada una asignación particular $(P, Q)$, definimos el costo total de combustible para reunir todos los coches en un punto $y$ como $\text{cost}(P, Q, y) = \sum_{i=0}^{N-1} \lvert X[P[i]] -y \rvert \times C[Q[i]]$.

Dado un punto entero $p$, definimos el costo de combustible en el peor de los casos en el punto $p$ como el costo total máximo de combustible sobre todas las posibles asignaciones $(P, Q)$. Es decir, definimos $\text{worst}(p) = \max\limits_{P,Q} \text{cost}(P, Q, p)$.

Su tarea es determinar un punto entero $p$ tal que el costo de combustible en el peor de los casos en el punto $p$, $\text{worst}(p)$, sea minimizado. Si hay múltiples puntos $p$ que alcanzan el mismo valor mínimo de $\text{worst}(p)$, puede informar cualquiera de ellos.

Detalles de implementación

Debe implementar el siguiente procedimiento:

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

• $N$: el número de coches.
• $X$: un arreglo de longitud $N$ que describe las posiciones de los coches ordenadas de forma creciente.
• $C$: un arreglo de longitud $N$ que describe las tasas de consumo de combustible de los coches ordenadas de forma creciente.
• Este procedimiento se llama exactamente una vez por cada caso de prueba.
• Este procedimiento debe devolver un entero $p$, para el cual el costo de combustible en el peor de los casos al reunir todos los coches en $p$ sea mínimo entre todos los puntos enteros.

Restricciones

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

Subtareas

1. (10 puntos) $N \le 1000, \lvert X[i] \rvert \le 10^3$.
2. (23 puntos) $N \le 100\;000$.
3. (17 puntos) $N \le 1\;000\;000$.
4. (31 puntos) $C[i] \le 1$, para todo $0 \leq i \leq N - 1$.
5. (19 puntos) Sin restricciones adicionales.

Ejemplos

Considere la siguiente llamada:

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

Suponga que $p = 1$. Entonces se puede demostrar que las asignaciones $P = [0,1,2]$ y $Q = [2,1,0]$ producen el costo de combustible en el peor de los casos. Es decir, $\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$. Tenga en cuenta que podría haber otras asignaciones de $P$ y $Q$ que produzcan el costo de combustible en el peor de los casos, tales como $P = [2,1,0]$ y $Q = [2,1,0]$.

También se puede demostrar que el punto entero $p = 1$ es el punto con el mínimo $\text{worst}(p)$ posible. Por lo tanto, esta llamada debe devolver 1.

Evaluador de muestra

Formato de entrada:

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

Formato de salida:

Un entero que representa el valor de retorno de car_gathering.