|
Лягушонок
(Время: 1 сек. Память: 16 Мб Сложность: 39%)
Многие, вероятно, слышали песни про приключения лягушонка Crazy Frog. На этот раз неугомонное милое создание решило подкрепиться, но даже такое простое действие решило выполнить в виде игры. Итак, в каждой клетке квадратного игрового поля, разбитого на N×N (N ≤ 50) клеток, находится один комар весом aij (вес комара – натуральное число ≤ 50), i - номер строки, j - номер столбца. Лягушонок, прыгая с клетки на клетку, ест комаров. Правила игры таковы - в каждом столбце можно съесть не более одного комара. Всякий раз при съедании комара запоминаем номер строки, откуда съеден комар, и сумма номеров строк, в которых были съедены комары, в конце игры должна быть в точности равна N. Учтите, если из какой-то строки съедено несколько комаров, то номер данной строки участвует в суммировании более одного раза.
Определите максимальный вес комаров, который можно съесть при следовании приведённым правилам.
Входные данные
Первая строка входного файла INPUT.TXT содержит число N. Следующие N строк содержат по N чисел aij, разделенных пробелами.
Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – вес съеденных комаров.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
8 2 1
1 2 6
2 7 2 | 14 |
| 2 | 5
8 2 1 2 3
1 2 6 2 4
2 7 2 3 4
1 3 2 4 4
1 3 4 3 1
| 19 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
