Free Goodies

Petra 和 Jan 得到了一箱免费的物品，他们希望将这些物品分配完毕。由于两人对每件物品的估值不同，公平地分配并不容易。

两人决定轮流从尚未被选择的物品中取走一件，直到所有物品都被取走。由抛硬币的结果决定谁先选择。

Petra 每次都会选择当前对自己价值最高的物品。如果有多件物品对她的价值相同，她会选择其中对 Jan 价值最低的物品。

Jan 的策略是使自己最终获得的物品总价值最大。如果有多种选择都能使他的最终总价值达到最大，他会选择其中能够使 Petra 最终获得的物品总价值最大的方案。

Petra 和 Jan 都清楚对方对每件物品的估值。给定所有物品的估值以及先手者，请计算分配结束后，Petra 和 Jan 各自获得的物品总价值。两人的总价值均按照各自对物品的估值计算。

输入格式

第一行包含一个正整数 $T$，表示测试数据的组数。

对于每组测试数据：

• 第一行包含一个整数 $n$，表示物品数量；
• 第二行包含一个字符串 Petra 或 Jan，表示先选择物品的人；
• 接下来 $n$ 行，第 $i$ 行包含两个整数 $p_i$ 和 $j_i$，分别表示 Petra 和 Jan 对第 $i$ 件物品的估值。

输出格式

对于每组测试数据，输出一行两个整数，分别表示 Petra 和 Jan 最终获得的物品总价值。

Petra 的总价值按照 $p_i$ 计算，Jan 的总价值按照 $j_i$ 计算。

样例输入

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

样例输出

170 130
14 16
9 10

数据范围

• $1\le T\le 100$；
• $1\le n\le 1000$；
• $0\le p_i,j_i\le 1000$。

来源与许可

本题题面与测试数据整理自 BZOJ 2264。

样例 1

输入

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

输出

170 130
14 16
9 10