This is the hard version of the maximum flow 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 data, $1 \leq n \leq 2\,000$, $1 \leq m \leq 3.2 \cdot 10^5$, $1 \leq c \leq 10^9$.