409078: GYM103430 K Ice Cream Van

Polycarp is a huge fan of ice cream. However, he lives in a small city of Bertown, where it's pretty hard to find new types of ice cream to try out.

Luckily for Polycarp, an ice cream van will be arriving to Bertown every day during the next $$$n$$$ days. Each day, the van will be bringing an infinite supply of one type of ice cream. The type of ice cream brought on the $$$i$$$-th day has a taste value of $$$a_i$$$.

Now Polycarp wants to come up with an integer value $$$x$$$ (the same for all $$$n$$$ days) and divide the types of ice cream into tasty and mediocre — an ice cream type will be considered tasty if its taste value is not less than $$$x$$$, otherwise it's mediocre. He proceeds with the following strategy on the $$$i$$$-th of the next $$$n$$$ days:

• if Polycarp has at least one ice cream left from previous days, he doesn't buy any ice cream on that day;
• otherwise, if $$$a_i < x$$$ (the ice cream that is being sold during this day is mediocre), then he buys $$$1$$$ ice cream and eats it on the $$$i$$$-th day;
• otherwise, he buys $$$k_i$$$ ice creams and eats one of them on each of the days $$$i, i+1, \dots, i+k_i-1$$$. He doesn't buy any more ice creams during these days. Thus, the next time he will visit the van on the day $$$i+k_i$$$, if that day doesn't exceed $$$n$$$. Note that $$$i+k_i$$$ might exceed $$$n$$$ — in that case, Polycarp still eats all $$$k_i$$$ ice creams he has already bought.

Polycarp estimates his happiness as the total taste value of the ice creams he eats. In particular, if he eats $$$k_i$$$ ice creams of the $$$i$$$-th type, then its taste value $$$a_i$$$ gets added to the happiness $$$k_i$$$ times.

What is the maximum happiness Polycarp can achieve by choosing the value of $$$x$$$?

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of days the van arrives.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the taste value of the ice cream on the $$$i$$$-th day.

The third line contains $$$n$$$ integers $$$k_1, k_2, \dots, k_n$$$ ($$$1 \le k_i \le n$$$) — the number of ice creams Polycarp wants to buy on the $$$i$$$-th day if the ice cream is tasty.

Print a single integer — the maximum happiness Polycarp can achieve by choosing the value of $$$x$$$.

5
7 3 5 9 3
2 5 5 1 3

39

4
4 2 1 3
2 2 2 2

15

4
4 2 1 3
1 1 1 1

10