Мальчик Петя мечтает вырасти и стать Главным Сантехником Берляндии. Уже сейчас он обдумывает задачи, которые ему наверняка придется решать в будущем. К сожалению, Петя еще слишком неопытен, и потому одну из таких задач (вызывающую у Пети наибольший интерес) предстоит решить Вам.
В столице Берляндии есть n резервуаров для воды, пронумерованных целыми числами от 1 до n. Эти резервуары некоторым образом соединены однонаправленными трубами, причем любая пара резервуаров соединена не более чем одной трубой в каждом из направлений. Каждая труба характеризуется своей толщиной — строго положительным целым числом, которое определяет, сколько литров воды в единицу времени эта труба может пропустить. Вода в город поступает из главного водохранилища, имеющего номер 1. Пройдя по некоторому пути из труб, она должна попасть в сточный резервуар, снабженный очистной системой (он имеет номер n).
Петя хочет увеличить толщину некоторого поднабора труб суммарно не более чем на k единиц толщины таким образом, чтобы толщина каждой трубы осталась целочисленной. Помогите ему определить, какое максимальное количество воды может протекать в единицу времени из главного водохранилища в сточный резервуар после осуществления такой операции.
Примечание
В первом тесте можно увеличить толщину трубы из 1-го во 2-ой резервуар на 7 единиц.
Во втором тесте толщину трубы из 1-го во 2-ой резервуар нужно увеличить на 4 единицы, из 2-го в 3-ий — на 3 единицы, из 3-го в 4-ый — на 2 единицы и из 4-ого в 5-ый — на 1 единицу.