Problem 3069 --Coins

3069: Coins

正确率: $0.00\%$ 下一题

Description

There are

n groups of coins, and the

i-th group contains two coins valued at

ai and

bi. Now you want to pick exactly

k coins out of them. However, there is a restriction - you can not pick the second coin valued at

bi in the

i-th group without picking the other one in the same group. In other words, in the

i-th group, you can
- pick none of the two coins;
- pick only the first one valued at

ai; or
- pick both of them.
We now want to know the maximum sum of the

k picked coins' values, denoted by

f(k).
Furthermore, we want to know

f(1),f(2),⋯,f(2n).

The input contains several test cases, and the first line contains a single integer

T (1≤T≤90), the number of test cases.

For each test case, the first line contains an integer

n (1≤n≤100000), indicating the number of coin groups.

Each of the following

n lines contains two integers

ai,bi (1≤ai,bi≤10000) indicating the coin values in that group.

It is guaranteed that the sum of

n in all test cases does not exceed

2100000.

For each test group, just output

2n integers in a single line representing

f(1),f(2),⋯,f(2n), and adjacent integers should be separated by one space.

4 6 9 11 12 14
3 5 7 9

竞赛编号	竞赛名称	竞赛时间	访问比赛