Hunting Monsters

A group of N monsters has invaded into the town. You, as a guardian of the town, should protect the town from the attack of those monsters. As you are a smart warrior, you are going to eliminate K of them so that all the remaining monsters are scared and let them quit the town themselves.

In order to defeat a monster, you should consume A unit of energy while you restore B unit of energy after defeating it. If your energy before attack is less than A, you will be exterminated and the town will be ruined. These values A and B depends on the monster, so they may be distinct for different monsters. You may arbitrarily choose monsters to be killed. Note that you can defeat monsters in any order. You want to know the minimum amount of initial energy needed to kill at least K monsters. You are required to calculate the answer for all K=1$ \cdots $N.

The first line of the input contains a single integer T (1≤T≤600), denoting the number of test cases. Each test case consists of 3 lines.

The first line of each test case contains a single integer N (1≤N≤$3 \cdot {10^5}$), the number of monsters. The next line contains N integers $A_i$ (1≤$A_i$≤$10^9$), the amount of energy needed to defeat the $i^{th}$ monster. The third line contains N integers $B_i$ (1≤$B_i$≤$10^9$), the amount of energy you will gain after killing the $i^{th}$ monster. It is guaranteed that the sum of N over all test cases does not exceed 2 500 000.

Let $ans_K$ be the least initial energy needed to defeat K monsters.

You should calculate all $ans_K$ for K=1$ \cdots $N. In order to avoid huge output, you are only required to get the following.

For each test case, print a single integer E in a single line.

2
3
2 3 1
1 5 4
4
1 2 3 4
1 1 2 3

6
30

For the first test case, ans[1,2,3]={1,1,1}.

For the second test case, ans[1,2,3,4]={1,2,3,4}.
For example, if you have 4 units of initial energy, you can kill the 4th, 3rd, 2nd and then 1st monster in order.
First you kill 4th monster, your energy will be 4-4+3=3.
Next, you attack 3rd monster, your energy will be 3-3+2=2.
After killing them, you kill 2nd one, then energy will become 2-2+1=1.
Finally, you can kill 1st one since your energy is not less than A_1.

2020 Multi-University Training Contest 1