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.
3
4
Mechthilf
100 80
70 80
50 80
30 50
4
Mechthilf
10 1
1 10
6 6
4 4
7
Trutbert
4 1
3 1
2 1
1 1
1 2
1 3
1 4
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 ShareAlike license (cc bysa).
Please log in to submit your solution.
Difficulty 

Average test runtime  0.20 
Points (changes over time)  10 
Tried by  2 users 
Solved by  2 users 
#  Name  Runtime  Points worth 

1  ,s/java/NaN/gi  0.19  10 
2  贝尔恩德  0.20  10 