题目描述

给你一个 $n$ 个点、$m$ 条有向边的有向图 $G$，每条边有流量下界 $l_i$ 和流量上界 $r_i$，以及源点 $s$ 和汇点 $t$。

求出源点 $s$ 到汇点 $t$ 的最小流量或报告无解。

输入格式

第一行两个正整数 $n,m,s,t$，表示图 $G$ 的点数和边数，以及源点编号和汇点编号。

接下来 $m$ 行每行四个正整数 $u_i,v_i,l_i,r_i$，分别表示每条有向边的起点和终点，以及流量下界和上界。

图可能会有重边和自环。

输出格式

输出源点 $s$ 到汇点 $t$ 的最小流量，若无解输出 N。

6 7 1 5
1 2 3 5
2 3 3 4
3 4 5 6
1 4 1 5
4 5 0 100000
6 3 0 1
4 6 1 2

5

6 6 4 1
4 1 0 5
4 2 0 6
4 3 0 7
2 2 3 3
5 6 1 1
6 5 2 2

N

提示

【样例解释 #1】

其中 $1$ 号点为源点，$5$ 号点为汇点。

【数据范围】

图可能会有重边和自环。

对于所有测试数据：$1\leq n\leq 10^3$，$1\leq s,t\leq n$，$1\leq m\leq 10^4$，$1\leq u_i,v_i\leq n$，$0\leq l_i\leq r_i\leq 10^5$。

保证 $s\neq t$。对于任意 $i$ 保证 $s\neq v_i$，$t\neq u_i$。