Juego Tradicional#11730

Juego Tradicional

2 segundos

256 megabytes

Muy difícil

Hace muchos años, cuando Chmyaaax aún no era malvado, le encantaba jugar un juego tradicional de las tribus del sistema planetario Link-Cut con Anton. El juego se desarrolla en un tablero de $1 \times n$ 1 \times n, donde cada celda contiene un par de números $a_{i}, b_{i}$ a_i, b_i, todos los números son distintos. También hay una pieza de juego que inicialmente está en la posición $1$ , y un equilibrio mágico que inicialmente es igual a $0$ . Los jugadores se turnan para hacer movimientos, siendo Chmyaaax quien juega primero.

Supongamos que la pieza de juego está actualmente en la celda $i$ .

En su turno, Chmyaaax puede mover la pieza hacia adelante $k$ celdas, donde $k > 0$ k>0, restando $k \cdot a_{i}$ k \cdot a_i monedas del equilibrio, y cambiando la posición de la pieza a $i + k$ i+k.
En su turno, Anton puede mover la pieza hacia atrás $k$ celdas, donde $k > 0$ k>0, agregando $k \cdot b_{i}$ k \cdot b_i monedas al equilibrio, y cambiando la posición de la pieza a $i - k$ i-k, o puede usar magia para mover la pieza a la última celda, agregando $(n - i) \cdot b_{i}$ (n−i) \cdot b_i monedas al equilibrio, y colocando la pieza en la posición $n$ .

En cualquier momento, la pieza no puede salir del tablero (es decir, su posición debe ser mayor que 0 y menor que $n + 1$ n+1). El juego termina cuando la pieza alcanza la celda $n$ . El objetivo de Chmyaaax es maximizar el equilibrio, mientras que el objetivo de Anton es minimizarlo. Si ambos jugadores juegan de manera óptima, ¿cuál será el equilibrio al final del juego? Se puede demostrar que bajo estas condiciones, el juego no continuará indefinidamente.

Entrada

La primera línea contiene un entero $n (2 \leq n \leq 1 0^{6})$ n(2 \le n \le 10^6) — el tamaño del tablero en el que se desarrolla el juego.

La segunda línea contiene $n$ enteros $a_{i} (- 1 0^{9} \leq a_{i} \leq 1 0^{9})$ a_i(-10^9 \le a_i \le 10^9).

La tercera línea contiene $n$ enteros $b_{i} (- 1 0^{9} \leq b_{i} \leq 1 0^{9})$ b_i(-10^9 \le b_i \le 10^9).

Para cada par de $i$ y $j$ , tal que $i \neq = j$ i \neq j y $1 \leq i, j \leq n$ 1 \le i,j \le n, se cumple que $a_{i} \neq = a_{j}$ a_i \neq a_j, $b_{i} \neq = b_{j}$ b_i \neq b_j, $a_{i} \neq = b_{i}$ a_i \neq b_i y $a_{i} \neq = b_{j}$ a_i \neq b_j.

Salida

Necesitas imprimir el valor del equilibrio al final del juego, si ambos jugadores juegan de manera óptima.

Ejemplos

Ejemplo

Ejemplo 1

Ejemplo 2

Nota

En el primer caso de prueba, para Chmyaaax es óptimo saltar desde el inicio hasta el final disminuyendo el equilibrio en $33 \cdot 7 = 231$ 33 \cdot 7 = 231, logrando un equilibrio de $- 231$ . Se podría probar que no hay ninguna estrategia para él, con la que pueda lograr un equilibrio mayor.

En el segundo caso de prueba, Chmyaaax puede saltar a la celda $2$ cambiando el equilibrio a $- 5 \cdot 2 = - 10$ -5 \cdot 2 = -10, Anton puede mover la pieza a la última celda, agregando al equilibrio $15 \cdot 2 = 30$ 15 \cdot 2 = 30, haciendo que el equilibrio sea igual a $20$ .

Puntuación

( $25$ puntos): $n \leq 20$ n \le 20;
( $30$ puntos): $n \leq 50$ n \le 50, $- 200 \leq a_{i}, b_{i} \leq 200$ -200 \le a_i, b_i \le 200;
( $40$ puntos): $n \leq 5000$ n \le 5000;
( $30$ puntos): $n \leq 1 0^{5}$ n \le 10^5;
( $75$ puntos): sin restricciones adicionales.