Фермер Джон недавно купил новую ферму, чтобы расширить свою империю
производства молока. Новая ферма соединена с ближайшим городом сетью труб,
и ФД хочет вычленить наилучшее подмножество этих труб для покупки с целью
передачи молока с фермы в город.
Сеть труб описывается \(N\) точками соединения (конечными точками труб),
последовательно пронумерованных \(1 \ldots N\) (\(2 \leq N \leq 1000\)).
Точка соединения 1 представляет новую ферму Джона, а точка соединения \(N\)
представляет город. Имеется \(M\) двунаправленных труб (\(1 \leq M \leq 1000\)),
каждая их которых соединяет две точки соединения. \(i\)-ая труба стоит \(c_i\)
долларов и может поддерживать передачу молока со скоростью \(f_i\) литров в
секунду.
ФД хочет купить один путь (самый выгодный) из труб, конечными точками которого
будут точки \(1\) и \(N\). Стоимость пути равна сумме стоимостей труб вдоль этого
пути. Скорость передачи молока по пути равна минимальной из скоростей передачи труб
(минимальное звено будет узким местом пути). ФД хочет максимизировать скорость
передачи, делённую на стоимость пути. Гарантируется существование пути из \(1\) в \(N\).
ОЦЕНИВАНИЕ:
- Тесты 2-5 удовлетворяют \(N,M\le 100.\)
ФОРМАТ ВВОДА (файл pump.in):
Первая строка ввода содержит \(N\) and \(M\). Каждая из последующих \(M\) строк
описывает трубу четырьмя целыми числами
\(a\) и \(b\) (две различные точки соединения, соединёнными этой трубой),
\(c\) (её стоимость),
\(f\) (её производительность - скорость передачи молока).
\(c\) и \(f\) оба положительные целые числа в интервале \(1 \ldots 1000\).
ФОРМАТ ВЫВОДА (файл pump.out):
Выведите оптимальное значение, умноженное на \(10^6\), обрезанное до целого
(то есть округлённое вниз до ближайшего целого числа, если это число не целое).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
2 1 2 4
2 3 5 3
|
428571
|