P7456 - King of Hot Pot

内存限制：128 MB 时间限制：1 S

题面：传统评测方式：文本比较上传者：

提交：2 通过：0

提交提交记录统计 Web Board

Little Q is enjoying hot pot together with Tangjz. There are n dishes of meat in the boiling water, labeled

by 1, 2, . . . , n. The i-th dish of meat will be OK to eat at time ai , and it will take Little Q bi units of

time to swallow it. You can assume swallowing a dish of meat won’t cost any time, and it is impossible

for Little Q to swallow more than one dish of meat at the same moment. Note that for the i-th dish of

meat, Little Q can choose to ignore it for a while and swallow it later.

Little Q is called “King of Hot Pot”, and he wants to show offff before Tangjz by swallowing k dishes of

meat as soon as possible. Please write a program to help Little Q fifind k dishes of meat and the order to

swallow them such that the time he spends on reaching the target is minimized for every possible value

of k (1 ≤ k ≤ n). Note that the time for waiting is also included in the answer.

The fifirst line of the input contains a single integer T (1 ≤ T ≤ 10 000), the number of test cases.

For each case, the fifirst line of the input contains an integer n (1 ≤ n ≤ 300 000), denoting the number of

dishes of meat.

Each of the following n lines contains two integers ai and bi (1 ≤ ai , bi ≤ 109 ), denoting each dish of meat.

It is guaranteed that the sum of all n is at most 1 000 000.

For each test case, output a single line containing n integers, the k-th (1 ≤ k ≤ n) of which denoting the

minimum possible units of time needed for Little Q to swallow k dishes of meat.

3 5 7 12 18

2020多校2

7456: King of Hot Pot