E. Петя и трубопровод
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мальчик Петя мечтает вырасти и стать Главным Сантехником Берляндии. Уже сейчас он обдумывает задачи, которые ему наверняка придется решать в будущем. К сожалению, Петя еще слишком неопытен, и потому одну из таких задач (вызывающую у Пети наибольший интерес) предстоит решить Вам.

В столице Берляндии есть n резервуаров для воды, пронумерованных целыми числами от 1 до n. Эти резервуары некоторым образом соединены однонаправленными трубами, причем любая пара резервуаров соединена не более чем одной трубой в каждом из направлений. Каждая труба характеризуется своей толщиной — строго положительным целым числом, которое определяет, сколько литров воды в единицу времени эта труба может пропустить. Вода в город поступает из главного водохранилища, имеющего номер 1. Пройдя по некоторому пути из труб, она должна попасть в сточный резервуар, снабженный очистной системой (он имеет номер n).

Петя хочет увеличить толщину некоторого поднабора труб суммарно не более чем на k единиц толщины таким образом, чтобы толщина каждой трубы осталась целочисленной. Помогите ему определить, какое максимальное количество воды может протекать в единицу времени из главного водохранилища в сточный резервуар после осуществления такой операции.

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

В первой строке заданы два целых числа n и k (2 ≤ n ≤ 50, 0 ≤ k ≤ 1000), разделенные пробелом. Далее следуют n строк по n целых чисел, разделенных единичными пробелами. В строке i + 1 в колонке j записано целое число cij — толщина трубы из резервуара i в резервуар j (0 ≤ cij ≤ 106, сii = 0). Если cij = 0, то трубы из резервуара i в резервуар j нет.

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

Выведите единственное целое число — максимальное количество воды, которое может протекать в единицу времени из главного водохранилища в сточный резервуар.

Примеры
Входные данные
5 7
0 1 0 2 0
0 0 4 10 0
0 0 0 0 5
0 0 0 0 10
0 0 0 0 0
Выходные данные
10
Входные данные
5 10
0 1 0 0 0
0 0 2 0 0
0 0 0 3 0
0 0 0 0 4
100 0 0 0 0
Выходные данные
5
Примечание

В первом тесте можно увеличить толщину трубы из 1-го во 2-ой резервуар на 7 единиц.

Во втором тесте толщину трубы из 1-го во 2-ой резервуар нужно увеличить на 4 единицы, из 2-го в 3-ий — на 3 единицы, из 3-го в 4-ый — на 2 единицы и из 4-ого в 5-ый — на 1 единицу.