Codeforces Round 212 (Div. 2) |
---|
Закончено |
Мальчик Петя мечтает вырасти и стать Главным Сантехником Берляндии. Уже сейчас он обдумывает задачи, которые ему наверняка придется решать в будущем. К сожалению, Петя еще слишком неопытен, и потому одну из таких задач (вызывающую у Пети наибольший интерес) предстоит решить Вам.
В столице Берляндии есть 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 единицу.
Название |
---|