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 in deciding what to
choose. When faced with a choice, Petra 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 Jan. (Since Petra and Jan are
good friends, they know exactly how much value the other places on
each goodie.)
Jan's strategy, however, consists of maximizing his own final
value. He is also very considerate, so if multiple choices lead to the
same optimal result, he prefers Petra to have as much final value as
possible.
You are given the result of the initial coin toss. After Jan and Petra
have finished dividing all the goodies between themselves, what is the
total value of the goodies each of them ends up with?
Input
On the first line a positive integer: the number of test cases, at
most 100. After that per test case:
One line with an integer n (1 ≤ n ≤ 1 000): the
number of goodies.
One line with a string, either "Petra" or "Jan": the
person that chooses first.
n lines with two integers pi and ji (0 ≤ pi,ji ≤ 1 000) each: the values that Petra and Jan assign to the
i-th goodie, respectively.
Output
Per test case:
One line with two integers: the value Petra gets and the value
Jan gets. Both values must be according to their own valuations.