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

Багато років тому, коли Чмяяякс ще не був злим, він любив грати в традиційну гру з племен планетної системи Link-Cut з Антоном. Гра проходить на дошці розміром $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_i$ та $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$ балів): без додаткових обмежень.