Dividing the Gems

Time limit1sMemory limit128 MB

Summary
Simulate an alternating gem-picking game where one player greedily picks by fixed rules while the other plays optimally to maximize his own total, tie-breaking for the opponent's total, and output final scores.
Level

Hard8 of 10

Topics
Greedy, Game theory, Sorting
Solved
No attempts yet

Problem

Petra and Jan want to share a box full of gems. Dividing it fairly is hard, because the two of them value each gem differently.

They take turns removing gems, one gem per turn, and repeat this until no gems remain. A coin flip decides who takes the first turn.

Petra and Jan follow different strategies.

  • On her turn, Petra takes the remaining gem she values the most. If several gems are tied for her highest value, she takes the one among them that Jan values the least.
  • Jan takes gems so that the total value he ends up with is as large as possible. If several choices achieve that maximum, he takes gems so that the total value Petra ends up with is also as large as possible.

Given who starts and how each person values every gem, compute the total gem value that each person finally collects.

Input

The first line contains the number of test cases TT (T≤100T \le 100). Each test case is given as follows.

  • The first line contains the number of gems nn (1≤n≤10001 \le n \le 1000).
  • The second line contains the name of the person who takes the first turn: Petra if Petra starts, or Jan if Jan starts.
  • Each of the next nn lines contains two integers, Petra's value pip_i and Jan's value jij_i for one gem (0≤pi,ji≤10000 \le p_i, j_i \le 1000).

Output

For each test case, print one line containing the total value Petra finally collects and the total value Jan finally collects, in that order, separated by a space.

Examples3

  1. Example 1

    Input
    3
4
Petra
100 80
70 80
50 80
30 50
4
Petra
10 1
1 10
6 6
4 4
7
Jan
4 1
3 1
2 1
1 1
1 2
1 3
1 4
    Expected output
    170 130
14 16
9 10

  2. Example 2

    Input
    2
1
Petra
5 7
1
Jan
5 7
    Expected output
    5 0
0 7

  3. Example 3

    Input
    2
4
Petra
10 1
1 10
6 6
4 4
4
Jan
10 1
1 10
6 6
4 4
    Expected output
    14 16
14 16