Максимальний потік мінімальної вартості

Вхідні дані

Перший рядок містить два цілих числа $n$ та $m$ — кількість вершин та кількість ребер у графі ( $2 \leq n \leq 100$ 2 \leq n \leq 100, $1 \leq m \leq 1000$ 1 \leq m \leq 1000). Кожен з наступних $m$ рядків містить чотири цілі числа: номери вершин, які з'єднує відповідне ребро, його пропускну здатність і його вартість. Пропускні здатності і вартості не перевищують $1 0^{5}$ 10^5.

Вихідні дані

Виведіть одне число — вартість максимального потоку мінімальної вартості з вершини 1 у вершину n. Відповідь не перевищує $2^{63} - 1$ 2^{63}-1. Гарантується, що в графі немає циклів від'ємної вартості.

Приклади

Приклад 1

Loading