Очередь

В магазине ABT («Amortized Binary Trees») стоят $n$ клиентов в очереди на позициях от $1$ до $n$. Время, необходимое кассиру для обслуживания $i$-го клиента, равно $t_i$.

Время, которое нужно провести в очереди клиенту, равно сумме времён, необходимых кассиру для обслуживания всех клиентов перед ним, плюс время, необходимое для обслуживания этого клиента. То есть, в очереди из $3$ человек с $t=[1,4,2]$ времена для каждого человека равны $1$, $1+4=5$ и $1+4+2=7$ соответственно.

Чтобы минимизировать сумму времён, которые клиентам нужно провести в очереди перед тем, как их обслужат, они согласились на переупорядочивание. Однако $i$-й клиент не хочет перемещаться на более, чем $a_i$ позиций назад от своей исходной позиции (но все не против перемещения вперед на любое количество позиций). Какова минимальная сумма времён, которую эти клиенты могут достичь?

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

Первая строка содержит одно целое число $n$ $(1\le n\le 10^5)$ — количество клиентов в очереди.

Вторая строка содержит $n$ целых чисел $t_1,t_2,\dots ,t_n$ $(1\le t_i\le 10^9)$ — количество времени, необходимое кассиру для обслуживания каждого клиента.

Третья строка содержит $n$ целых чисел $a_1,a_2,\dots ,a_n$ $(0\le a_i\le n-i)$ — максимальное количество позиций, на которое каждый клиент согласен переместиться назад.

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

В единственной строке необходимо вывести минимальную сумму времён ожидания, которую можно достичь.

Примеры

Примечание

В первом примере существует два допустимых способа перераспределения клиентов:

1. $1$-й, $2$-й и $3$-й (никого не перемещаем);

2. $2$-й, $1$-й и $3$-й;

3. $2$-й, $3$-й и $1$-й;

4. $3$-й, $2$-й и $1$-й.

Сумма времен в этих случаях равна:

1. $2+(2+4)+(2+4+1)=2+6+7=15$;

2. $4+(4+2)+(4+2+1)=17$;

3. $4+(4+1)+(4+1+2)=16$;

4. $1+(1+4)+(1+4+2)=13$.

Как мы видим, лучший ответ здесь — $13$. Можно показать, что другого возможного расположения людей в этой очереди не существует.

Во втором примере оба человека могут находиться на любой позиции, поэтому оба их возможных расположения допустимы и дают равные ответы: $1+(1+1)=3$.

В третьем примере можно показать, что ни одного из людей нельзя переместить, и их единственное допустимое расположение — исходное. Сумма времени, которую люди проведут в этой очереди, равна $1+3+6+10+15=35$.

Оценивание

1. ($3$ балла): $a_i=0$ для всех $i$ $(1\le i\le n)$;

2. ($7$ баллов): $n\le 10$;

3. ($8$ баллов): $n\le 20$;

4. ($6$ баллов): $a_i=n-i$ для всех $i$ $(1\le i\le n)$;

5. ($18$ баллов): $n\le 4000$;

6. ($13$ баллов): $t_i\le 100$ для всех $i$ $(1\le i\le n)$;

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