Задачи очного тура региональной олимпиады по информатике

Для игры используется `N` карточек, на каждой из которых записано целое положительное число. На первом этапе карточки перемешиваются и кладутся на стол числами вниз. Первый игрок («жадина») случайно берет по две карточки из кучи, карточку с большим числом он забирает себе, а карточку с меньшим числом – отдает второму игроку. В случае равенства чисел одну карточку он берет себе, а другую отдает сопернику. При распределении второй игрок видит обе карточки. После того как все карточки распределены, начинается второй этап игры («наказание»). Ход делает всегда первый игрок. Первый игрок кладет на стол числом вверх любую карточку по своему выбору из имеющихся у него на руках. Второй игрок смотрит на карточку, положенную первым игроком, и отвечает, выкладывая одну из своих карточек по собственному выбору. Игрок, который положил карточку с большим числом, забирает обе карточки и кладет в свою кучу выигранных карт. Эти карточки далее не участвуют в игре. Если игроки положили карточки с одинаковыми числами, то каждый забирает обратно свою карточку и кладет ее в кучу выигранных карт. Когда на руках у игроков не останется карт, они считают сумму чисел на выигранных картах. Побеждает игрок с большей суммой.

Напишите программу, которая вычислит результат игры при условии, что каждый из игроков стремится максимизировать свой выигрыш и не ошибается.

В первой строке ввода содержится одно целое четное число `N\ (2≤N≤200)` – количество карт. Далее следует `N/2` строк, в которых описывается в каком порядке вытаскивались карточки из кучи на первом этапе игры, в каждой строке содержится два целых числа в диапазоне от 1 до 1000, разделенных пробелом – числа на паре карточек, вытащенных первым игроком.

В выходной файл вывести два целых числа через пробел – суммы на выигранных карточках для первого и второго игрока.

6
4 3
5 5
1 2

6 14