Задан ориентированный граф, каждое ребро которого обладает пропускной способностью и стоимостью. Найдите максимальный поток минимальной стоимости из вершины с номером \textbf{1} в вершину с номером \textbf{n}. \InputFile Первая строка входного файла содержит \textbf{n} и \textbf{m} - количество вершин и количество ребер графа (\textbf{2} ≤ \textbf{n} ≤ \textbf{100}, \textbf{1 }≤ \textbf{m} ≤ \textbf{1000}). Следующие \textbf{m} строк содержат по четыре целых числа числа: номера вершин, которые соединяет соответствующее ребро графа, его пропускную способность и его стоимость. Пропускные способности и стоимости не превосходят \textbf{10^5}. \OutputFile В выходной файл выведите одно число - цену максимального потока минимальной стоимости из вершины с номером \textbf{1} в вершину с номером \textbf{n}. Ответ не превышает \textbf{2^63-1}. Гарантируется, что в графе нет циклов отрицательной стоимости.