eolymp
bolt
Try our new interface for solving problems
Məsələlər

Crazy frog

Crazy frog

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Многие, вероятно, слышали песни о приключениях лягушонка Crazy Frog. На этот раз неугомонное милое создание решило подкрепиться, но даже такое простое действие решило выполнить в виде игры. Итак, в каждой клетке квадратного игрового поля, разбитого на N*N (N <= 50) клеток, находится комар весом a_ij (вес комара – натуральное число <= 50), i - номер строки, j - номер столбца. Лягушонок, прыгая с клетки на клетку, ест комаров. Правила игры таковы - в каждом столбце можно съесть не более одного комара. Всякий раз при съедании комара запоминаем номер строки, откуда съеден комар, и сумма номеров строк, в которых были съедены комары, в конце игры должна быть в точности равна N. Учтите, если из какой-то строки съедено несколько комаров, то номер данной строки участвует в суммировании более одного раза.

Определите максимальный вес комаров, который можно съесть при следовании приведённым правилам.

Giriş verilənləri

Первая строка входа содержит количество тестов. Первая строка каждого теста содержит число N. Следующие N строк содержат по N чисел a(i, j), разделенных пробелами.

Çıxış verilənləri

Для каждого теста в выходной файл выводится число, равное весу съеденных комаров.

Nümunə

Giriş verilənləri #1
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
Çıxış verilənləri #1
14
19