Традиционная игра

Много лет назад, когда Чмяяякс еще не был злым, он любил играть в традиционную игру из племен планетной системы Линк-Кат с Антоном. Игра проходит на доске размером $1\times n$, где каждая ячейка содержит пару чисел $a_i,b_i$, все числа различны. Также есть игровая фишка, которая изначально находится на позиции $1$, и магический счет, который изначально равен $0$. Игроки поочередно делают ходы, Чмяяякс ходит первым.

Предположим, что игровая фишка в данный момент находится на ячейке $i$.

1. В свой ход Чмяяякс может переместить фишку вперед на $k$ ячеек, где $k>0$, вычитая $k\cdot a_i$ монет из счета и изменяя позицию фишки на $i+k$.

2. В свой ход Антон может переместить фишку назад на $k$ ячеек, где $k>0$, добавляя $k\cdot b_i$ монет к счету и изменяя позицию фишки на $i-k$, или он может использовать магию, чтобы переместить фишку на последнюю ячейку, добавляя $(n-i)\cdot b_i$ монет к балансу и устанавливая фишку на позицию $n$.

В любой момент времени фишка не может выйти за пределы доски (т.е., ее позиция должна быть больше 0 и меньше $n+1$). Игра заканчивается, когда фишка достигает ячейки $n$. Цель Чмяяякса — максимизировать баланс, в то время как цель Антона — минимизировать его. Если оба игрока будут играть оптимально, каков будет баланс в конце игры? Можно доказать, что при этих условиях игра не будет продолжаться бесконечно.

Входные данные

Первая строка содержит одно целое число $n(2\le n\le 10^6)$ — размер доски, на которой происходит игра.

Вторая строка содержит $n$ целых чисел $a_i(-10^9\le a_i\le 10^9)$.

Третья строка содержит $n$ целых чисел $b_i(-10^9\le b_i\le 10^9)$.

Для каждой пары $i$ и $j$, таких что $i\ne j$ и $1\le i,j\le n$, выполняется $a_i\ne a_j$, $b_i\ne b_j$ и $a_i\ne b_j$.

Выходные данные

Необходимо вывести значение баланса в конце игры, если оба игрока играют оптимально.

Примеры

Примечание

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

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

Оценивание

1. ($25$ баллов): $n\le 20$;

2. ($30$ баллов): $n\le 50$, $-200\le a_i,b_i\le 200$;

3. ($40$ баллов): $n\le 5000$;

4. ($30$ баллов): $n\le 10^5$;

5. ($75$ баллов): без дополнительных ограничений.