#319 Maximum Flow

Statement

Statement language

You are given a directed network with vertices numbered from $1$ to $N$ . Find the maximum flow from vertex $S$ to vertex $T$ . Parallel edges, self-loops, and edges with zero capacity are allowed.

Input

The input is given in the following format:

$N\ M\ S\ T$ $u_1\ v_1\ c_1$

Output

Print the maximum flow.

Constraints

$2 \leq N \leq 400$ .
$0 \leq M \leq 10\,000$ .
$1 \leq u_{i}, v_{i} \leq$ ().

Subtasks

#	Score	Constraints
1	20	$N \leq 20$ ; $M \leq 100$ ; $c_i \leq 20$ ().

Samples

Input

Output

10110