Традиційна гра#11730

Традиційна гра

2 секунди

256 мегабайтів

Дуже складна

Багато років тому, коли Чмяяякс ще не був злим, він любив грати в традиційну гру з племен планетної системи Link-Cut з Антоном. Гра проходить на дошці розміром $1 \times n$ 1 \times n, де кожна клітинка містить пару чисел $a_{i}, b_{i}$ a_i, b_i, всі числа різні. Є також ігрова фішка, яка спочатку знаходиться на позиції $1$ , і магічний рахунок, який спочатку дорівнює $0$ . Гравці по черзі роблять ходи, Чмяяякс ходить першим.

Припустимо, що ігрова фішка зараз знаходиться в клітинці $i$ .

У свій хід Чмяяякс може перемістити фішку вперед на $k$ клітин, де $k > 0$ k > 0, віднімаючи $k \cdot a_{i}$ k \cdot a_i монет з рахунка, і змінюючи позицію фішки на $i + k$ i + k.
У свій хід Антон може перемістити фішку назад на $k$ клітин, де $k > 0$ k > 0, додаючи $k \cdot b_{i}$ k \cdot b_i монет до рахунку, і змінюючи позицію фішки на $i - k$ i - k, або він може використати магію, щоб перемістити фішку на останню клітинку, додавши $(n - i) \cdot b_{i}$ (n - i) \cdot b_i монет до рахунку, і встановивши фішку на позицію $n$ .

У будь-який момент часу фішка не може виходити за межі дошки (тобто, її позиція повинна бути більшою за $0$ і меншою за $n + 1$ n + 1). Гра закінчується, коли фішка досягає клітинки $n$ . Мета Чмяяякса — максимізувати рахунок, тоді як мета Антона — мінімізувати його. Якщо обидва гравці грають оптимально, яким буде рахунок у кінці гри? Можна довести, що за цих умов гра не триватиме нескінченно.

Вхідні дані

Перший рядок містить одне ціле число $n$ ( $2 \leq n \leq 1 0^{6}$ 2 \le n \le 10^6) — розмір дошки, на якій проходить гра.

Другий рядок містить $n$ цілих чисел $a_{i}$ a_i ( $- 1 0^{9} \leq a_{i} \leq 1 0^{9}$ -10^9 \le a_i \le 10^9).

Третій рядок містить $n$ цілих чисел $b_{i}$ b_i ( $- 1 0^{9} \leq b_{i} \leq 1 0^{9}$ -10^9 \le b_i \le 10^9).

Для кожної пари $i$ та $j$ , такої що $i \neq = j$ i \neq j і $1 \leq i, j \leq n$ 1 \le i, j \le n, виконується $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 та $a_{i} \neq = b_{j}$ a_i \neq b_j.

Вихідні дані

Вам потрібно вивести значення рахунку в кінці гри, якщо обидва гравці грають оптимально.

Приклади

Приклад

Приклад 1

Приклад 2

Примітка

У першому тестовому прикладі для Чмяяякса оптимально стрибнути з початку до кінця, зменшуючи баланс на $33 \cdot 7 = 231$ 33 \cdot 7 = 231, досягнувши балансу $- 231$ . Можна довести, що немає жодної стратегії для нього, з якою він може досягти більшого балансу.

У другому тестовому прикладі Чмяяякс може стрибнути на клітинку $2$ , змінивши баланс на $- 5 \cdot 2 = - 10$ -5 \cdot 2 = -10, Антон може перемістити фішку на останню клітинку, додавши до балансу $15 \cdot 2 = 30$ 15 \cdot 2 = 30, в результаті чого баланс дорівнює $20$ .

Оцінювання

( $25$ балів): $n \leq 20$ n \le 20;
( $30$ балів): $n \leq 50$ n \le 50, $- 200 \leq a_{i}, b_{i} \leq 200$ -200 \le a_i, b_i \le 200;
( $40$ балів): $n \leq 5000$ n \le 5000;
( $30$ балів): $n \leq 1 0^{5}$ n \le 10^5;
( $75$ балів): без додаткових обмежень.