G. Sneaking Sprinkles
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice is preparing cupcakes for a bake-sale! She has $$$N$$$ cupcakes, each with $$$A_i$$$ sprinkles initially on them. She is almost finished decorating the cupcakes, she just has to add $$$N$$$ more layers, each with $$$B_i$$$ sprinkles, to every cupcake. She cannot change the order in which she adds the layers. Unbeknownst to Alice, Bob loves sprinkles and hopes to take some off the cupcakes without her noticing. In fact, every time Alice adds a layer of sprinkles to the cupcakes, Bob will go to the cupcake with the most sprinkles on it and take half of its sprinkles for himself (rounded down). If Bob repeats this process after every layer of sprinkles is added, how many total sprinkles will there be left on Alice's cupcakes?

Input

The first line of input contains an integer $$$N$$$, the number of cupcakes and the number of sprinkle layers to add. The second line of input will contain the array $$$A$$$ with $$$N$$$ values, the initial amount of sprinkles on the $$$i-th$$$ cupcake. The third line of input will contain the array $$$B$$$ with $$$N$$$ values, the number of sprinkles added on the $$$i-th$$$ layer.

$$$ 1 \leq N \leq 5 \cdot 10^4 $$$ , $$$ 1 \leq A_i \leq 10^9 $$$ , $$$ 1 \leq B_i \leq 10^9 $$$

Output

Output a single integer, the total number of sprinkles left on Alice's cupcakes

Example
Input
4
1 2 9 12
3 2 6 4
Output
54
Note

After Alice adds the first layer, the cupcakes have 4, 5, 12, and 15 sprinkles respectively. Then Bob takes 7 sprinkles from the 4th cupcake. Then Alice adds 2 sprinkles to every cupcake, etc.