Черга

У магазині 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$ балів): без додаткових обмежень.