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?
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 a single integer, the total number of sprinkles left on Alice's cupcakes
41 2 9 123 2 6 4
54
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.
