Бесплатные подарки
Петра и Ян только что получили коробку с бесплатными подарками и хотят поделить их между собой. Однако сделать это справедливо не так просто, поскольку они оценивают каждый подарок по-разному.
Чтобы разделить подарки, они решили использовать следующий метод: они выбирают подарки по очереди, пока все подарки не будут распределены. Для определения, кто будет выбирать первый подарок, подбрасывается монета.
У Петра и Яна разные стратегии выбора. Когда Петра делает выбор, она всегда выбирает подарок, который для нее наиболее ценен. В случае равенства она выбирает тот, который наименее ценен для Яна. (Поскольку Петра и Ян хорошие друзья, они точно знают, насколько каждый из них ценит каждый подарок.)
Стратегия Яна заключается в максимизации его собственного окончательного значения. Он также очень внимателен, поэтому, если несколько вариантов приводят к одному и тому же оптимальному результату, он предпочитает, чтобы у Петры было как можно больше окончательной ценности.
Вам дан результат начального подбрасывания монеты. После того как Ян и Петра закончат делить все подарки между собой, какова будет общая ценность подарков, которые каждый из них получит?
Входные данные
На первой строке указано положительное целое число: количество тестов, не более 100. Далее для каждого теста:
Одна строка с целым числом n (1 ≤ n ≤ 1000): количество подарков.
Одна строка со строкой, либо "Petra" либо "Jan": человек, который выбирает первым.
n строк с двумя целыми числами p_i и j_i (0 ≤ p_i, j_i ≤ 1000) каждое: значения, которые Петра и Ян присваивают i-му подарку соответственно.
Выходные данные
Для каждого теста:
Одна строка с двумя целыми числами: значение, которое получает Петра, и значение, которое получает Ян. Оба значения должны соответствовать их собственным оценкам.