Hunting Monsters
TimeLimit:3000MS MemoryLimit:524288KB
64-bit integer IO format:%I64d
未提交 | 登录后收藏
Problem Description
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.
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.
Input
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.
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.
Output
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.
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.
SampleInput
2 3 2 3 1 1 5 4 4 1 2 3 4 1 1 2 3
SampleOutput
6
30
Hint 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.