Каскад Токтогульской ГЭС
Токтогульское водохранилище на реке Нарын — крупнейшее в Центральной Азии. Из него вода идёт через каскад гидроэлектростанций и сеть каналов к полям Ферганской долины.

Токтогульское водохранилище. Фото: Benjamin Goetzinger, CC BY-SA 4.0, Wikimedia Commons
Инженер Талант моделирует распределение воды на сутки. Сеть состоит из n узлов (водохранилище — узел 1, главный распределительный узел в долине — узел n) и m каналов. Канал j ведёт воду только в одном направлении — из узла u[j] в узел v[j]. Через него нужно пропустить целое количество x[j] кубометров воды, причём
l[j] ≤ x[j] ≤ c[j],
где c[j] — пропускная способность канала, а l[j] — экологический минимум: меньше этого количества пропускать нельзя, иначе пересохнет русло и погибнет рыба. Перекачка одного кубометра по каналу j стоит w[j] сомов.
В каждом промежуточном узле (кроме 1 и n) сколько воды втекает, столько и вытекает. Из узла 1 должно вытечь (с учётом воды, которая в него возвращается по каналам) ровно F кубометров, и ровно столько же должно поступить в узел n.
Найдите минимальную суммарную стоимость такого распределения или выведите -1, если выполнить все требования невозможно.
Входные данные
В первой строке — три целых числа n, m, F (2 ≤ n ≤ 200, 1 ≤ m ≤ 3000, 0 ≤ F ≤ 10⁹).
В каждой из следующих m строк — пять целых чисел u[j], v[j], l[j], c[j], w[j] (1 ≤ u[j], v[j] ≤ n, u[j] ≠ v[j], 0 ≤ l[j] ≤ c[j] ≤ 10⁹, 0 ≤ w[j] ≤ 1000). Между двумя узлами может быть несколько каналов, в том числе встречных.
Выходные данные
Выведите одно целое число — минимальную стоимость или -1.
Пример 1
Вход:
4 5 6
1 2 0 5 1
1 3 2 4 3
2 4 0 4 2
3 4 0 6 1
2 3 0 3 1
Выход:
20
Пример 2
Вход:
4 5 10
1 2 0 5 1
1 3 2 4 3
2 4 0 4 2
3 4 0 6 1
2 3 0 3 1
Выход:
-1
Пояснение
В первом примере по каналу 1 → 3 нужно пустить не меньше 2 кубометров (стоимость пути 1 → 3 → 4 — 4 сома за кубометр). Остальные 4 кубометра выгоднее пустить по пути 1 → 2 → 4 за 3 сома: всего 2 · 4 + 4 · 3 = 20.
Во втором примере из узла 1 можно выпустить не более 5 + 4 = 9 кубометров.
Система оценивания
| Подзадача | Баллы | Дополнительные ограничения |
|---|---|---|
| 1 | 10 | n ≤ 5, m ≤ 7, c[j] ≤ 3 |
| 2 | 25 | все l[j] = 0 |
| 3 | 20 | n ≤ 50, m ≤ 500 |
| 4 | 45 | без дополнительных ограничений |
Баллы за подзадачу начисляются, только если пройдены все её тесты.
Комментарии