Jeu Traditionnel#11730

Jeu Traditionnel

2 secondes

256 mégaoctets

Très difficile

Il y a de nombreuses années, lorsque Chmyaaax n'était pas encore maléfique, il aimait jouer à un jeu traditionnel des tribus du système planétaire Link-Cut avec Anton. Le jeu se déroule sur un plateau de $1 \times n$ 1 \times n, où chaque cellule contient une paire de nombres $a_{i}, b_{i}$ a_i, b_i, tous les nombres sont distincts. Il y a aussi un pion qui est initialement à la position $1$ , et une balance magique qui est initialement égale à $0$ . Les joueurs jouent à tour de rôle, Chmyaaax jouant en premier.

Supposons que le pion soit actuellement sur la cellule $i$ .

À son tour, Chmyaaax peut déplacer le pion de $k$ cellules vers l'avant, où $k > 0$ k > 0, en soustrayant $k \cdot a_{i}$ k \cdot a_i pièces de la balance, et en changeant la position du pion à $i + k$ i + k.
À son tour, Anton peut déplacer le pion de $k$ cellules vers l'arrière, où $k > 0$ k > 0, en ajoutant $k \cdot b_{i}$ k \cdot b_i pièces à la balance, et en changeant la position du pion à $i - k$ i - k, ou il peut utiliser la magie pour déplacer le pion à la dernière cellule, ajoutant $(n - i) \cdot b_{i}$ (n - i) \cdot b_i pièces à la balance, et plaçant le pion à la position $n$ .

À tout moment, le pion ne peut pas sortir du plateau (c'est-à-dire que sa position doit être supérieure à $0$ et inférieure à $n + 1$ n + 1). Le jeu se termine lorsque le pion atteint la cellule $n$ . L'objectif de Chmyaaax est de maximiser la balance, tandis que l'objectif d'Anton est de minimiser celle-ci. Si les deux joueurs jouent de manière optimale, quelle sera la balance à la fin du jeu ? Il peut être prouvé que dans ces conditions, le jeu ne continuera pas indéfiniment.

Entrée

La première ligne contient un entier $n$ ( $2 \leq n \leq 1 0^{6}$ 2 \le n \le 10^6) — la taille du plateau sur lequel le jeu se déroule.

La deuxième ligne contient $n$ entiers $a_{i}$ a_i ( $- 1 0^{9} \leq a_{i} \leq 1 0^{9}$ -10^9 \le a_i \le 10^9).

La troisième ligne contient $n$ entiers $b_{i}$ b_i ( $- 1 0^{9} \leq b_{i} \leq 1 0^{9}$ -10^9 \le b_i \le 10^9).

Pour chaque paire de $i$ et $j$ , telle que $i \neq = j$ i \neq j et $1 \leq i, j \leq n$ 1 \le i, j \le n, il est vrai 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_{j}$ a_i \neq b_j et pour chaque $i$ ( $1 \leq i \leq n$ 1 \le i \le n), $a_{i} \neq = b_{i}$ a_i \neq b_i.

Sortie

Vous devez afficher la valeur de la balance à la fin du jeu, si les deux joueurs jouent de manière optimale.

Exemples

Exemple

Exemple 1

Exemple 2

Note

Dans le premier exemple de test, pour Chmyaaax, il est optimal de sauter du début à la fin en diminuant la balance de $33 \cdot 7 = 231$ 33 \cdot 7 = 231, atteignant une balance de $- 231$ . Il peut être prouvé qu'il n'existe aucune stratégie pour lui, avec laquelle il peut atteindre une balance plus élevée.

Dans le deuxième exemple de test, Chmyaaax peut sauter à la cellule $2$ , changeant la balance à $- 5 \cdot 2 = - 10$ -5 \cdot 2 = -10, Anton peut déplacer le pion à la dernière cellule, ajoutant à la balance $15 \cdot 2 = 30$ 15 \cdot 2 = 30, rendant la balance égale à $20$ .

Notation

( $25$ points): $n \leq 20$ n \le 20;
( $30$ points): $n \leq 50$ n \le 50, $- 200 \leq a_{i}, b_{i} \leq 200$ -200 \le a_i, b_i \le 200;
( $40$ points): $n \leq 5000$ n \le 5000;
( $30$ points): $n \leq 1 0^{5}$ n \le 10^5;
( $75$ points): pas de contraintes supplémentaires.