Crazy Frog

Багато з вас, напевно, чули пісні про пригоди жабенятка Crazy Frog. Цього разу енергійна істота вирішила підкріпитися, але навіть таку просту дію перетворила на гру. Отже, на квадратному ігровому полі розміром N \times N (N \leq 50) у кожній клітинці знаходиться комар вагою a_{ij} (натуральне число $\le 50$), де $i$ — номер рядка, $j$ — номер стовпця. Жабеня стрибає з клітинки на клітинку, поїдаючи комарів. Правила гри такі: у кожному стовпці можна з’їсти не більше одного комара. Кожного разу, коли з’їдається комар, запам’ятовується номер рядка, і до кінця гри сума всіх номерів рядків, у яких було з’їдено комарів, повинна дорівнювати $N$. Зверніть увагу: якщо з одного рядка з’їдено декілька комарів, цей номер враховується відповідну кількість разів.

Визначте максимальну сумарну вагу комарів, яку можна з’їсти, дотримуючись цих правил.