printРабочее место участника

printЗадачи

1752. Crazy Frog

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Многие, вероятно, слышали песни про приключения лягушонка Crazy Frog. На этот раз неугомонное милое создание решило подкрепиться, но даже такое простое действие решило выполнить в виде игры. Итак, в каждой клетке квадратного игрового поля, разбитого на `N*N` (`N\ ≤\ 50`) клеток, находится комар весом `a_{ij}` (вес комара – натуральное число ≤ 50), `i` – номер строки, `j` – номер столбца. Лягушонок, прыгая с клетки на клетку, ест комаров. Правила игры таковы – в каждом столбце можно съесть не более одного комара. Всякий раз при съедании комара запоминаем номер строки, откуда съеден комар, и сумма номеров строк, в которых были съедены комары, в конце игры должна быть в точности равна `N`. Учтите, если из какой-то строки съедено несколько комаров, то номер данной строки участвует в суммировании более одного раза.
Определите максимальный вес комаров, который можно съесть при следовании приведённым правилам.
Первая строка входа содержит количество тестов. Первая строка каждого теста содержит число `N`. Следующие `N` строк содержат по `N` чисел `a_{ij}`, разделенных пробелами.
Для каждого теста в выходной файл выводится число, равное весу съеденных комаров.

Пример ввода

2
3
8 2 1 
1 2 6 
2 7 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

Пример вывода

14
19
Четвертьфинальные соревнования Чемпионата мира Восточно-сибирского региона, 2008
loading