7456: King of Hot Pot

内存限制:128 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:2 通过:0

题目描述

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.

输入样例 复制

15
1 2
4 6
3 5
4 2
3 2

输出样例 复制

3 5 7 12 18

分类标签