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:
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
Name |
---|