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