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 .
## Input
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.
## Output
Print one integer — the minimum total sum of changes that Sasha has to do in order to get the correct flow description.
[samples]
## Note
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.
在莫斯科国立大学计算机力学系硕士入学考试中，Sasha 被问到了 Ford-Fulkerson 算法的问题。他对此主题非常熟悉，因为在编程竞赛中他多次使用过该算法。作为问题的任务，他被给定一个具有部分构建流的网络，需要用它来演示算法的工作流程。他迅速写完了文本，但当他查看题目时，发现给定的网络是错误的！
假设你被给定一个有向图 #cf_span[G(V, E)]，其中有两个特殊节点 #cf_span[s] 和 #cf_span[t]，分别称为源点和汇点。我们用 #cf_span[n] 表示图中的节点数，即 #cf_span[n = |V|]，用 #cf_span[m] 表示图中有向边的数量，即 #cf_span[m = |E|]。在本题中，我们始终将节点 #cf_span[1] 视为源点，节点 #cf_span[n] 视为汇点。此外，对于图中的每条边 #cf_span[e]，我们定义容量函数 #cf_span[c(e)] 和流函数 #cf_span[f(e)]。函数 #cf_span[f(e)] 表示一个正确的流，当且仅当满足以下条件：
显然，由于考试是昨晚临时准备的，题目中存在大量错误。Sasha 请求一位教授修正网络或给出正确的题目，但得到的回复是：硕士生应当能够自己修正网络。由于教授不希望题目变得简单，他要求 Sasha 以最小化总修改次数的方式修正网络。Sasha 不允许移除边、添加新边或反转现有边的方向。他唯一能做的就是修改容量函数 #cf_span[c(e)] 和流函数 #cf_span[f(e)]，且所有值必须保持为非负整数。对流是否最大没有要求。
请找出 Sasha 为使流合法所需对函数 #cf_span[f(e)] 和 #cf_span[c(e)] 进行的最小总修改量。总修改量定义为绝对差值之和，即若新函数为 #cf_span[f * (e)] 和 #cf_span[c * (e)]，则总修改量为 。
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[2 ≤ n ≤ 100], #cf_span[0 ≤ m ≤ 100]) —— 分别表示图中的节点数和边数。接下来的 #cf_span[m] 行每行包含一条边的描述，由四个整数 #cf_span[ui], #cf_span[vi], #cf_span[ci] 和 #cf_span[fi] (#cf_span[1 ≤ ui, vi ≤ n], #cf_span[ui ≠ vi], #cf_span[0 ≤ ci, fi ≤ 1 000 000]) 组成，分别表示边的起点、终点、当前容量和流值。
节点 #cf_span[1] 是源点，节点 #cf_span[n] 是汇点。保证没有边指向源点，也没有边从汇点出发。
给定图中不含自环，但可能包含重边。
请输出一个整数 —— Sasha 为获得合法流描述所需进行的最小总修改量。
## Input
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[2 ≤ n ≤ 100], #cf_span[0 ≤ m ≤ 100]) —— 分别表示图中的节点数和边数。接下来的 #cf_span[m] 行每行包含一条边的描述，由四个整数 #cf_span[ui], #cf_span[vi], #cf_span[ci] 和 #cf_span[fi] (#cf_span[1 ≤ ui, vi ≤ n], #cf_span[ui ≠ vi], #cf_span[0 ≤ ci, fi ≤ 1 000 000]) 组成，分别表示边的起点、终点、当前容量和流值。节点 #cf_span[1] 是源点，节点 #cf_span[n] 是汇点。保证没有边指向源点，也没有边从汇点出发。给定图中不含自环，但可能包含重边。
## Output
请输出一个整数 —— Sasha 为获得合法流描述所需进行的最小总修改量。
[samples]
## Note
在第一个测试用例中，流初始时即为合法。注意，流不必是最大流。在第二个测试用例中，唯一一条边的流值大于其容量。有两种修复方式：将容量增加至 #cf_span[2]，或将流值减少至 #cf_span[1]。在第三个测试用例中，仅有 #cf_span[1] 单位的流流入顶点 #cf_span[2]，但有 #cf_span[2] 单位的流流出。一种可能的解决方案是将第二条边的流值减少 #cf_span[1]。在第四个测试用例中，存在孤立的流循环，但根据定义，这种描述是合法的。
**Definitions**
Let $ G = (V, E) $ be a directed graph with $ |V| = n $, $ |E| = m $.
Let $ s = 1 $ be the source and $ t = n $ be the sink.
For each edge $ e = (u, v) \in E $, we are given capacity $ c(e) \in \mathbb{Z}_{\geq 0} $ and flow $ f(e) \in \mathbb{Z}_{\geq 0} $.
We seek new functions $ c^*(e), f^*(e) \in \mathbb{Z}_{\geq 0} $ minimizing $ \sum_{e \in E} \left( |c^*(e) - c(e)| + |f^*(e) - f(e)| \right) $, subject to:
**Constraints**
1. **Capacity constraint**: $ 0 \leq f^*(e) \leq c^*(e) $ for all $ e \in E $.
2. **Flow conservation**: For all $ v \in V \setminus \{s, t\} $,
$$
\sum_{e \in \delta^-(v)} f^*(e) = \sum_{e \in \delta^+(v)} f^*(e)
$$
where $ \delta^+(v) $ and $ \delta^-(v) $ are the sets of outgoing and incoming edges at $ v $, respectively.
3. **No flow into source or out of sink**:
$$
\sum_{e \in \delta^-(s)} f^*(e) = 0, \quad \sum_{e \in \delta^+(t)} f^*(e) = 0
$$
**Objective**
Minimize
$$
\sum_{e \in E} \left( |c^*(e) - c(e)| + |f^*(e) - f(e)| \right)
$$