Безкоштовні подарунки#2450
Петра і Ян щойно отримали коробку з безкоштовними подарунками і хочуть поділити їх між собою. Однак зробити це справедливо не так просто, адже кожен з них по-різному цінує різні подарунки.
Для поділу подарунків вони вирішили скористатися наступною процедурою: вони по черзі обирають подарунок, поки всі подарунки не буде вибрано. Для визначення, хто вибирає першим, підкидають монетку.
У Петра і Яна різні стратегії. Коли Петра робить вибір, вона завжди обирає подарунок, який для неї найцінніший. У разі рівності найвищої цінності, вона обирає той, що найменш цінний для Яна. (Оскільки Петра і Ян хороші друзі, вони точно знають, як інший оцінює кожен подарунок.)
Стратегія Яна — максимізувати свою підсумкову цінність. Він також уважний — якщо декілька варіантів дають однаковий оптимальний результат для нього, він віддає перевагу тому, щоб Петра отримала якнайбільшу підсумкову цінність.
Вам відомо, хто виграв початковий жереб. Після того, як всі подарунки поділені, яку підсумкову цінність отримав кожен із них?
У першому рядку позитивне ціле число: кількість тестових випадків, не більше . Далі для кожного тестового випадку:
Один рядок з цілим числом (1 \le n \le 1000): кількість подарунків.
Один рядок з рядком, або "Petra", або "Jan": той, хто вибирає першим.
рядків; у кожному два цілих числа p_i і j_i (0 \le p_i, j_i \le 1000): цінність -го подарунка для Петри і для Яна відповідно.
Для кожного тестового випадку:
Один рядок із двома цілими числами: цінність, яку отримала Петра, і цінність, яку отримав Ян, відповідно до власної оцінки.
Приклад 1