Вася и Петя играют в следующую
игру. Имеется доска размером N x N клеток. На каждой клетке лежит
фишка, на которой написана её стоимость. Игра ведётся следующим образом. Первый
игрок выбирает строку, содержащую хотя бы одну фишку. Второй игрок выбирает
столбец и забирает себе фишку из клетки на пересечении этой строки и столбца.
На следующем ходу игроки меняются местами − то есть уже второй игрок
будет выбирать строку, а первый − столбец. Затем игроки снова меняются, и
так далее. Игра заканчивается, когда фишек на доске не остаётся.
Во время игры участники
придерживаются следующей стратегии. Игрок, который выбирает строку, хочет,
чтобы его сопернику досталась как можно более дешёвая фишка. Но при этом он
знает и учитывает тот факт, что соперник всегда выбирает столбец так, чтобы
забрать в выбранной строке самую дорогую фишку.
Определите, какие суммы
наберут Вася и Петя по окончании игры. Начинает выбирать строку Вася.
Входные данные
В первой строке входных данных записано
целое четное число N (1 ≤ N ≤ 200). Затем идут N строк по N разделенных пробелом натуральных
чисел − стоимости фишек (в диапазоне от 1 до 100).
Выходные данные
Выведите два
числа через пробел − суммы стоимостей фишек у Васи и у Пети по окончании
игры.
|
Пример ввода
2
1
3
2
4
Пример вывода
3
7
|
Система
оценивания.
Решения,
верно работающее при N ≤ 50, будут оцениваться из 60 баллов.
