Mechthilf and Trutbert have recently taken part in a tombola. One day, long since having forgotten all about it, they find a package in the mail, full of goodies. They decide to divide the goodies, but since they value different goodies differently that's not exactly an easy task.

They settle upon the following procedure: they start by writing down how much each goodie is worth to them. Then, they start choosing goodies, one by one, in turn, until none are left. A coin is tossed to decide who gets to choose the first goodie.

Mechthilf and Trutbert have different strategies for deciding which goodie to choose. Mechthilf always selects the goodie that is most valuable to her. In case of a tie, she is very considerate and picks the one that is least valuable to Trutbert. Trutbert's strategy consists of maximizing his own final value. He is also very considerate, so if multiple choices lead to the same optimal result, he prefers Mechthilf to have as much final value as possible.

You are given the result of the initial coin toss. After Mechthilf and Trutbert have finished diving all the goodies between themselves, what is the total value of the goodies each of them ends up with?


The first line of the input contains an integer \(1 \leq t \leq 100\). \(t\) test cases follow, each of them separated by a blank line.

Each test case starts with a line containing an integer \(1 \leq n \leq 1000\), the number of goodies. The next line contains a string, either Mechthilf or Trutbert, the person who chooses first. \(n\) more lines follow, each containing two integers \(0 \leq m_i, t_i \leq 1000\) separated by a space, the values that Mechthilf and Trutbert assign to the \(i\)-th goodie, respectively.


For each test case, print a line containing m t, where \(m\) is the value Mechthilf gets, and \(t\) is the value Trutbert gets. Both values must be according to their respective valuations.

Sample Input

100 80
70 80
50 80
30 50

10 1
1 10
6 6
4 4

4 1
3 1
2 1
1 1
1 2
1 3
1 4

Sample Output

170 130
14 16
9 10

This problem is based on a problem first published at the Technische Universität München and is licensed under a Creative Commons Attribution Share-Alike license (cc by-sa).

Upload Solution

Please log in to submit your solution.


Difficulty (2 votes)
Average test runtime 0.20
Points (changes over time) 10
Tried by 2 users
Solved by 2 users

Global ranking

# Name Runtime Points worth
1 ,s/java/NaN/gi 0.19 10
2 贝尔恩德 0.20 10