В заданому орієнтованому графі знайти максимальний потік мінімальної вартості з вершини \(1\) у вершину \(N\).

Формат вхідних даних

В першому рядку два цілих числа \(N,M\) кількість вершин та дуг графа (\(1 \le N \le 400\) , \(0 \le M \le 15000\))
В кожному з наступних \(M\) рядків міститься по 4 числа \(V1,V2,W,C\) що означає наявність дуги з вершини \(V1\) у вершину \(V2\) пропускною здатністю \(W\) і ціною за одницию потоку \(C\). (\(W \ge 0\))

Гарантується, що вхідні дані, проміжні результати та відповідь знаходяться в проміжку 32-бітного знакового цілого числа

Формат вихідних даних

Виведіть два числа через пропуск: величину максимального потока і мінімальну його вартість.

Приклад вхідних даних-1

4 5
1 2 1 8
1 3 2 2
3 2 1 3
2 4 1 2
3 4 1 2

Приклад вихідних даних-1

2 11

Приклад вхідних даних-2

8 23
2 3 2147483647 1
1 3 1 1
2 4 2147483647 2
1 4 1 2
2 8 2 0
3 5 2147483647 3
1 5 1 3
3 6 2147483647 4
1 6 1 4
3 8 2 0
3 2 2147483647 0
4 6 2147483647 5
1 6 1 5
4 7 2147483647 6
1 7 1 6
4 8 2 0
4 2 2147483647 0
5 8 0 0
5 2 2147483647 0
6 8 0 0
6 2 2147483647 0
7 8 0 0
7 2 2147483647 0

Приклад вихідних даних-2

6 24