Maximum flow of minimum cost

Given a directed graph where each edge has a specified capacity and cost, your task is to determine the maximum flow with the minimum cost from vertex 1 to vertex n.

Input

The first line of the input contains two integers, n and m, representing the number of vertices and edges in the graph, respectively (2 ≤ n ≤ 100, 1 ≤ m ≤ 1000). Each of the following m lines provides four integers: the start vertex, the end vertex of the edge, its capacity, and its cost. Both capacities and costs are limited to a maximum of 10^5.

Output

Output a single integer, which is the cost of the maximum flow with the minimum cost from vertex 1 to vertex n. The result will not exceed 2^63-1. It is assured that the graph does not contain any negative cost cycles.

Examples