Description

给定一张n个点m条边的网络流图，其中源点和汇点的编号分别为1和n。 初始给定的每条边e包含四个信息(u_e,v_e,f_e,c_e )，分别是边的起点、终点、流量和容量。 但是，这张网络流图可能是不对的，例如有些边可能会出现f_e>c_e的情况，并且有些非源汇点流入和流出的流量不相等。 你需要修改每条边的容量和流量，但你不希望做太大的改动：如果边e的流量和容量分别调整为f_e^'和c_e^'，则这条边产生的代价就是|f_e^'-f_e |+|c_e^'-c_e |。 怎么修改，才能让所有边的代价之和最小呢？输出最小代价。

Format

Input

第一行包含两个整数n,m，代表点数和边数。

接下来m行，每行四个整数u_i,v_i,f_i,c_i，描述一条边。保证u_i≠v_i。

n,m≤100,0≤c_i,f_i≤10000

Output

一行，代表最小代价

Samples

3 3
1 2 1 1
2 3 2 2
1 3 3 3

1