Free Goodies#2450
Petra and Jan have just received a box full of free goodies, and want to divide the goodies between them. However, it is not easy to do this fairly, since they both value different goodies differently.
To divide the goodies, they have decided upon the following procedure: they choose goodies one by one, in turn, until all the goodies are chosen. A coin is tossed to decide who gets to choose the first goodie.
Petra and Jan have different strategies. When Petra makes a choice, she always selects the goodie that is most valuable to her. In case of a tie, she picks the one that is least valuable to Jan. (Since Petra and Jan are good friends, they know exactly how much value the other places on each goodie.)
Jan's strategy is to maximize his own final value. He is also considerate—if several options yield the same optimal result, he prefers Petra to obtain as much final value as possible.
You are given the result of the initial coin toss. After dividing all the goodies, what is the total value each of them obtains?
On the first line, a positive integer: the number of test cases, at most . After that, for each test case:
One line with an integer (1 \le n \le 1000): the number of goodies.
One line with a string, either "Petra" or "Jan": the person who chooses first.
lines, each with two integers p_i and j_i (0 \le p_i, j_i \le 1000): the values Petra and Jan assign to the -th goodie, respectively.
For each test case:
One line with two integers: the value Petra gets and the value Jan gets, according to their own valuations.
Example 1