e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Максимальный поток минимальной стоимости

Максимальный поток минимальной стоимости

Задан ориентированный граф, каждое ребро которого обладает пропускной способностью и стоимостью.

Найдите максимальный поток минимальной стоимости из вершины с номером 1 в вершину с номером n.

Входные данные

Первая строка входного файла содержит n и m - количество вершин и количество ребер графа (2n100, 1 m1000). Следующие m строк содержат по четыре целых числа числа: номера вершин, которые соединяет соответствующее ребро графа, его пропускную способность и его стоимость. Пропускные способности и стоимости не превосходят 105.

Выходные данные

В выходной файл выведите одно число - цену максимального потока минимальной стоимости из вершины с номером 1 в вершину с номером n. Ответ не превышает 263-1. Гарантируется, что в графе нет циклов отрицательной стоимости.

Time limit 2 seconds
Memory limit 64 MiB
Input example #1
4 5
1 2 1 2
1 3 2 2
3 2 1 1
2 4 2 1
3 4 2 3
Output example #1
12