This is a simple version of the maximum flow problem. You can expect a correctly implemented Dinic's algorithm or other similar algorithms to pass this problem.

Given $n$ nodes and $m$ edges, with the capacity of each edge provided, find the maximum flow from node $s$ to node $t$.

Input

The first line contains four integers $n, m, s, t$.

The next $m$ lines each contain three integers $u, v, c$, representing an edge from $u$ to $v$ with capacity $c$.

Output

Output the maximum flow from node $s$ to node $t$.

Examples

Input 1

7 14 1 7
1 2 5
1 3 6
1 4 5
2 3 2
2 5 3
3 2 2
3 4 3
3 5 3
3 6 7
4 6 5
5 6 1
6 5 1
5 7 8
6 7 7

Output 1

14

Subtasks

For all test cases, $1 \leq n \leq 500$, $1 \leq m \leq 20\,000$, $1 \leq c \leq 10^9$.