Remote Training on Programming

Выставка компьютерных фирм проходит в зале, разделенном на N ´ N павильонов. Каждая из четырех стен любого павильона, кроме граничных стен, имеет дверь в соседний павильон. Каждый павильон занят какой-либо фирмой, которая раздает посетителям предметы какого-либо одного вида (ручки, пакеты, проспекты и т.д.). Начинающий компьютерный бизнесмен Вася желает набрать бесплатных предметов на возможно большую сумму. К сожалению, в одни руки выдают только по одному предмету за одно посещение, поэтому Вася вынужден постоянно переходить из павильона в павильон. Посещать один и тот же павильон можно сколько угодно раз. На получение одного предмета Васе требуется одна минута. Требуется определить максимальную сумму, на которую Вася может набрать предметов в течение K минут. Зал определяется квадратной матрицей, содержащей стоимость предметов, выдаваемых в каждом павильоне. , 2 £ N £ 100, 0 < a_ij <10 000,

a_ij ÎZ

Путь Васи всегда начинается с павильона (1,1) и состоит из последовательности пар координат (i₁, j₁), (i₂, j₂),… ,(i_K, j_K), 1 £ K £ 10 000, в которой для любого t 1 £ t < K  1 £ i_t, j_t £ N и . По данным N, K и матрице A найти (i_t, j_t), t=1..K такие, что i₁ = j₁ = 1 и сумма  максимальна.

Входные и выходные данные

Первая строка входного файла содержит числа N и K. Следующие N строк представляют 1,2,…,N-ю строки матрицы, по N чисел в строке.

Выходной файл должен содержать единственное число — максимальную сумму.

 

Пример входного файла: 5 7 1 1 1 1 1 1 1 3 1 9 1 1 6 1 1 1 1 3 1 1 1 1 1 1 1

Соответствующий выходной файл: 21