보석 분배

Petra와 Jan은 보석으로 가득 찬 상자를 함께 나누어 가지려고 한다. 하지만 두 사람이 각 보석에 매기는 가치가 서로 다르기 때문에, 공정하게 나누는 일은 쉽지 않다.

두 사람은 턴을 번갈아 가며 한 번에 보석을 하나씩 가져가고, 남은 보석이 없을 때까지 이 과정을 반복한다. 누가 먼저 시작할지는 동전을 던져 정한다.

Petra와 Jan은 서로 다른 전략으로 보석을 고른다.

• Petra는 남은 보석 중에서 자신이 매긴 가치가 가장 큰 보석을 고른다. 그런 보석이 여러 개라면, 그중에서 Jan이 매긴 가치가 가장 작은 보석을 고른다.
• Jan은 자신이 최종적으로 얻는 가치의 합이 최대가 되도록 보석을 고른다. 그렇게 되는 선택이 여러 가지라면, 그중에서 Petra가 최종적으로 얻는 가치의 합이 가장 커지도록 고른다.

먼저 시작하는 사람과 두 사람이 각 보석에 매긴 가치가 주어질 때, 두 사람이 최종적으로 가져가는 보석 가치의 합을 각각 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$ ($T \le 100$)가 주어진다. 각 테스트 케이스는 다음과 같이 구성된다.

• 첫째 줄: 보석의 개수 $n$ ($1 \le n \le 1000$)
• 둘째 줄: 먼저 턴을 시작하는 사람의 이름. Petra가 먼저 시작하면 Petra, Jan이 먼저 시작하면 Jan이 주어진다.
• 이어지는 $n$개의 줄: 각 줄에 보석 하나에 대한 Petra가 매긴 가치 $p_i$와 Jan이 매긴 가치 $j_i$가 공백으로 구분되어 주어진다 ($0 \le p_i, j_i \le 1000$).

각 테스트 케이스마다 한 줄에, Petra가 최종적으로 가져가는 가치의 합과 Jan이 최종적으로 가져가는 가치의 합을 공백으로 구분하여 순서대로 출력한다.