e-olymp
Problems

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

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

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

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

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

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

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

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

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