题目描述

Berland 的冬天总是大雪纷飞。首都有 $n$ 个路口和 $m$ 条单向道路。第 $i$ 条道路从路口 $x_i$ 指向路口 $y_i$，道路上有 $w_i$ 吨积雪。

政府雇佣了公司 Snow White 清理积雪。公司每天派出一辆清雪车：

• 清雪车从路口 $A$ 出发；
• 沿道路方向行驶，最终到达路口 $B$ 并结束当天工作；
• 一天的路线可以重复经过同一条道路，也可以重复经过任意路口，包括 $A$ 和 $B$；
• 每经过一条道路一次，就清除该道路 $1$ 吨积雪；
• 如果某条道路已经没有积雪，则清雪车不能再经过这条道路。

部分道路具有历史价值，称为历史道路。所有历史道路都必须被完全清理，即最终这些道路的积雪必须变成 $0$。普通道路则不要求清空。

保证路口 $A$ 位于历史中心：忽略道路方向后，仅沿历史道路步行，可以从 $A$ 到达任意一条历史道路。

政府按工作天数向 Snow White 支付费用，因此公司希望在满足上述要求的前提下，工作的天数尽可能多。

在所有满足以下要求的工作安排中，求公司最多能够工作多少天：

1. 每天清雪车从 $A$ 出发并最终到达 $B$；
2. 每次经过道路时该道路仍有至少 $1$ 吨积雪；
3. 所有历史道路最终必须被完全清空。

只需要输出最大工作天数，不需要输出每天的具体路线。

输入格式

第一行包含四个整数 $n,m,A,B$：

• $2\le n\le100$；
• $0\le m\le5000$；
• $1\le A,B\le n$；
• $A\ne B$。

接下来 $m$ 行，每行四个整数 $x_i,y_i,w_i,t_i$，表示一条从 $x_i$ 指向 $y_i$ 的单向道路：

• $1\le x_i,y_i\le n$，且 $x_i\ne y_i$；
• $0\le w_i\le100$，表示道路上的积雪吨数；
• $t_i\in\{0,1\}$；
  • $t_i=0$ 表示普通道路；
  • $t_i=1$ 表示历史道路。

同一方向的两个路口之间至多有一条道路。

保证忽略方向后，仅沿历史道路可以从 $A$ 到达任意历史道路。

输出格式

输出一个整数 $p$，表示能够工作的最大天数。

如果不存在满足历史道路清理要求的工作安排，输出 $0$。

样例 1

4 7 1 4
1 2 3 1
2 1 100 0
2 4 1 0
1 3 1 0
3 4 4 0
2 3 2 1
1 4 2 0

6

样例 2

3 3 1 2
1 3 2 0
3 2 3 0
1 2 1 0

3