CF708D.Incorrect Flow

At the entrance examination for the magistracy of the MSU Cyber-Mechanics Department Sasha got the question about Ford-Fulkerson algorithm. He knew the topic perfectly as he worked with it many times on programming competition. As the task for the question he was given a network with partially build flow that he had to use in order to demonstrate the workflow of the algorithm. He quickly finished to write the text and took a look at the problem only to understand that the given network is incorrect!

Suppose you are given a directed graph G(V, E) with two special nodes s and t called source and sink. We denote as n the number of nodes in the graph, i.e. n = |V| and m stands for the number of directed edges in the graph, i.e. m = |E|. For the purpose of this problem we always consider node 1 to be the source and node n to be the sink. In addition, for each edge of the graph e we define the capacity function c(e) and flow function f(e). Function f(e) represents the correct flow if the following conditions are satisfied:

1. For each edge the flow is non-negative and does not exceed capacity c(e), i.e. 0 ≤ f(e) ≤ c(e).
2. For each node , that is not source or sink (v ≠ s and v ≠ t) the sum of flows of all edges going in v is equal to the sum of the flows among all edges going out from v. In other words, there is no flow stuck in v.

It was clear that as the exam was prepared last night and there are plenty of mistakes in the tasks. Sasha asked one of the professors to fix the network or give the correct task, but the reply was that the magistrate student should be able to fix the network himself. As the professor doesn't want the task to become easier, he asks Sasha to fix the network in a such way that the total number of changes is minimum possible. Sasha is not allowed to remove edges, add new ones or reverse the direction of existing edges. The only thing he is able to do is to change capacity function c(e) and flow function f(e). Moreover, all the values should remain non-negative integers. There is no requirement on the flow to be maximum in any sense.

Find the minimum possible total change of the functions f(e) and c(e) that Sasha has to make in order to make the flow correct. The total change is defined as the sum of absolute differences, i.e. if new functions are f * (e) and c * (e), then the total change is .

在莫斯科国立大学网络力学系硕士入学考试中，萨沙被问到了关于福特-富尔克森（Ford-Fulkerson）算法的问题。他对这一主题非常熟悉，因为曾在多次编程竞赛中实践过。作为该问题的具体任务，他被给出一个已部分构造好流值的网络，需以此演示该算法的执行流程。他很快写完了解答文字，但再仔细审题时却发现：所给网络是不合法的！

假设你被给定一个有向图 $ G(V, E) $，其中包含两个特殊节点 $ s $ 和 $ t $，分别称为源点（source）和汇点（sink）。记图中节点数为 $ n $，即 $ n = |V| $；边数为 $ m $，即 $ m = |E| $。在本题中，我们恒将节点 $ 1 $ 视为源点，节点 $ n $ 视为汇点。此外，对图中每条边 $ e $，定义其容量函数 $ c(e) $ 和流量函数 $ f(e) $。函数 $ f(e) $ 构成一个合法流，当且仅当满足以下两个条件：

1. 对每条边 ，流值非负且不超过其容量，即 $ 0 \leq f(e) \leq c(e) $。
2. 对每个既非源点也非汇点的节点 （即 $ v \ne s $ 且 $ v \ne t $），所有指向 $ v $ 的边的流量之和等于所有从 $ v $ 出发的边的流量之和。换言之，节点 $ v $ 上无流量滞留。

显然，这份考卷是昨夜仓促准备的，题目中存在大量错误。萨沙向一位教授提出请求，请其修正该网络或更换为正确题目，但得到的答复是：硕士生应具备自行修正网络的能力。 而为避免题目难度降低，教授要求萨沙以最少的总修改次数完成修正。萨沙不得删除边、添加新边，也不得反转已有边的方向；他唯一被允许的操作是修改容量函数 $ c(e) $ 和流量函数 $ f(e) $ 的取值。此外，所有修改后的值必须仍为非负整数。本题不要求最终流为最大流。

请计算萨沙为使该流合法所需进行的函数 $ f(e) $ 和 $ c(e) $ 的最小总修改量。此处“总修改量”定义为各边修改量的绝对值之和，即：若修改后的函数为 $ f^(e) $ 和 $ c^(e) $，则总修改量为 。

The first line of the input contains two integers n and m (2 ≤ n ≤ 100, 0 ≤ m ≤ 100) — the number of nodes and edges in the graph respectively. Each of the following m lines contains the description of the edges, consisting of four integers u__i, v__i, c__i and f__i (1 ≤ u__i, v__i ≤ n, u__i ≠ v__i, 0 ≤ c__i, f__i ≤ 1 000 000) — index of the node the edges starts from, the index of the node the edge goes to, current capacity and flow value.

Node number 1 is the source, and node number n is the sink. It's guaranteed that no edge goes to the source, and no edges starts in the sink.

Given graph contains no self-loops but may contain multiple edges.

输入的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 100$，$0 \leq m \leq 100$），分别表示图中的节点数和边数。接下来的 $m$ 行每行描述一条边，包含四个整数 $u_i$、$v_i$、$c_i$ 和 $f_i$（$1 \leq u_i,\,v_i \leq n$，$u_i \neq v_i$，$0 \leq c_i,\,f_i \leq 1\,000\,000$），分别表示该边的起点节点编号、终点节点编号、当前容量和当前流量值。

节点编号 $1$ 为源点（source），节点编号 $n$ 为汇点（sink）。保证不存在指向源点的边，也不存在从汇点出发的边。

给定图中不含自环边，但可能包含重边。

Print one integer — the minimum total sum of changes that Sasha has to do in order to get the correct flow description.

输出一个整数——Sasha 为获得正确的流描述所需进行的总改动量的最小值。

In the first sample, the flow is initially correct. Note, that the flow is not maximum, but this is not required.

In the second sample, the flow value of the only edge is greater than its capacity. There are two ways to fix this: either increase the capacity up to 2 or reduce the flow down to 1.

In the third sample, there is only 1 unit of flow coming to vertex 2, but there are 2 units going out of it. One of the possible solutions is to reduce the value of the flow on the second edge by 1.

In the fourth sample, there is isolated circulation of flow, but this description is correct by definition.

在第一个样例中，流初始时是正确的。注意，该流并非最大流，但题目并不要求其为最大流。

在第二个样例中，唯一一条边上的流量值超过了其容量。修复该问题有两种方式：要么将该边的容量提升至 2，要么将该边上的流量减少至 1。

在第三个样例中，仅有 1 单位流量流入顶点 2，但有 2 单位流量从该顶点流出。一种可行的解决方案是将第二条边上的流量值减少 1。

在第四个样例中，存在孤立的流循环，但根据定义，这种描述是正确的。