Description

给定 $n$ 个点，$m$ 条有向边，给定每条边的容量，保证每条边 $(u,v,w)$ 满足 $v-u\in[0,k]$，求从点 $1$ 到点 $n$ 的最大流。

Input Format

第一行包含三个正整数 $n$、$m$、$k$，用空格分隔。

接下来$m$行每行包含三个正整数 $u_i$、$v_i$、$w_i$，用空格分隔，表示第 $i$ 条有向边从 $u_i$ 出发，到达 $v_i$，容量为 $w_i$。

Output Format

一个整数，表示 $1$ 到 $n$ 的最大流。

9 21 3
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
1 3 1
2 4 1
3 5 1
4 6 1
5 7 1
6 8 1
7 9 1
1 4 1
2 5 1
3 6 1
4 7 1
5 8 1
6 9 1

3

5 10 2
3 5 73
3 4 33
3 5 84
4 5 10
3 4 15
1 2 83
1 3 8
1 3 24
5 5 15
1 2 62

32

Hint

对于 $20\%$ 的数据满足 $n\leq 10^2$，$m\leq 10^4$，$k\leq 2$。

对于 $40\%$ 的数据满足 $n\leq 10^4$，$m\leq 10^6$，$k\leq 2$。

对于 $60\%$ 的数据满足 $n\leq 8\times 10^4$，$m\leq 10^6$，$k\leq 2$。

对于 $80\%$ 的数据满足 $n\leq 8\times 10^4$，$m\leq 10^6$，$k\leq 4$。

对于 $100\%$ 的数据满足 $2\leq n\leq 8\times 10^4$，$1\leq m\leq 10^6$，$2\leq k\leq 7$，$1\leq w\leq100$。