На ферме Джона имеется сеть из M труб (1 <= M <= 500) для передачи молока от фермы к молокохранилищу. ФД хочет удалить и заменить некоторые из труб, но оставить ровно один путь, так чтобы он смог по прежнему передавать молоко из амбара в хранилище.
Сеть труб описывается N точками соединения (1 <= N <= 500), каждая из которых может служить конечной точкой множества труб. Точка соединения номер 1 - это амбар, а точка соединения номер N - молокохранилище. Каждая из M двунаправленных труб соединяет пару точек соединения и имеет время задержки - (количество времени, которое требуется чтобы молоко достигло одного конца из другого) пропускную способность - количество молока в единицу времени, которое может быть передано по этой трубе. Пары точек соединения могут соединяться более чем одной трубой.
Для пути от амбара к хранилищу время задержки - это сумма всех времен задержки всех труб в этом пути. А пропускная способность пути - минимум из пропускных способностей всех труб этого пути. Если ФД хочет передать X единиц молока через путь с временем задержки L и пропускной способностью C, то требуемое время равно L + X/C.
По заданной структуре сети труб ФД помогите ему выделить один путь от амбара к хранилищу, который позволит ему передать X единиц молока за минимальное количество времени.
PROBLEM NAME: mroute
Формат входных данных
* Строка 1: Три разделенных пробелом целых числа: N M X (1 <= X <= 1,000,000).
* Строки 2..1+M: Каждая строка описывает трубу 4-мя целыми числами: I J L C. I и J (1 <= I,J <= N) точки соединения обоих концов трубы L и C (1 <= L,C <= 1,000,000) задают время задержки и пропускную способность трубы.
Формат выходных данных
* Строка 1: Минимальное количество времени, которое потребуется чтобы передать молоко по единственному пути, округленное вниз до ближашего целого.
Примечание
Путь 1->3 занимает 14 + 15/1 = 29 единиц времени. Путь 1->2->3 занимает 20 + 15/2 = 27.5 единиц времени, и поэтому оптимальный.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 15
1 2 10 3
3 2 10 2
1 3 14 1
|
27
|