Перекачування молока#10290

Перекачування молока

1 секунда

128 мегабайтів

Середня

Фермер Джон нещодавно придбав нову ферму, щоб розширити свою молочну імперію. Ця ферма з'єднана з сусіднім містом мережею труб, і Джон хоче визначити найкращий набір труб для перекачування молока з ферми до міста.

Мережа трубопроводів складається з $n$ точок з'єднання (кінцевих точок труб), пронумерованих від $1$ до $n$ . Точка з'єднання $1$ є фермою Джона, а точка з'єднання $n$ — містом. Існує $m$ двонаправлених труб, кожна з яких з'єднує дві точки з'єднання. $i$ -та труба коштує $c_{i}$ c_i доларів, і Джон може її придбати для використання, причому вона підтримує швидкість потоку $f_{i}$ f_i літрів молока в секунду.

Джон прагне придбати труби для одного маршруту, що з'єднує точки $1$ і $n$ . Вартість маршруту — це сума вартостей труб уздовж нього. Швидкість потоку на маршруті визначається мінімальною пропускною здатністю труб на цьому маршруті (оскільки вона є вузьким місцем для потоку). Джон хоче максимізувати відношення пропускної здатності до вартості маршруту. Гарантується, що існує принаймні один шлях від $1$ до $n$ .

Вхідні дані

Перший рядок містить числа $n$ ( $2 \leq n \leq 1000$ 2 \le n \le 1000) і $m$ ( $1 \leq m \leq 1000$ 1 \le m \le 1000). Кожен з наступних $m$ рядків описує трубу чотирма цілими числами: $a$ і $b$ (два різних з'єднання, з'єднаних трубою), $c$ (вартість) і $f$ (пропускна здатність). Вартість і пропускна здатність є натуральними числами в діапазоні від $1$ до $1000$ .

Вихідні дані

Виведіть оптимальну відповідь, помножену на $1 0^{6}$ 10^6, усічену до цілого числа (тобто округлену до найближчого меншого цілого числа, якщо це число саме не є цілим).

Приклади

Приклад 1

Примітка

У прикладі є лише один шлях від $1$ до $n$ . Його пропускна здатність дорівнює $min (3, 4) = 3$ \min(3, 4) = 3, а вартість дорівнює $2 + 5 = 7$ 2 + 5 = 7.