{"raw_statement":[{"iden":"statement","content":"\n给定 $n$ 个点，$m$ 条有向边，给定每条边的容量，保证每条边 $(u,v,w)$ 满足 $v-u\\in[0,k]$，求从点 $1$ 到点 $n$ 的最大流。"},{"iden":"input","content":"第一行包含三个正整数 $n$、$m$、$k$，用空格分隔。\n\n接下来$m$行每行包含三个正整数 $u_i$、$v_i$、$w_i$，用空格分隔，表示第 $i$ 条有向边从 $u_i$ 出发，到达 $v_i$，容量为 $w_i$。"},{"iden":"output","content":"一个整数，表示 $1$ 到 $n$ 的最大流。"},{"iden":"note","content":"对于 $20\\%$ 的数据满足 $n\\leq 10^2$，$m\\leq 10^4$，$k\\leq 2$。\n\n对于 $40\\%$ 的数据满足 $n\\leq 10^4$，$m\\leq 10^6$，$k\\leq 2$。\n\n对于 $60\\%$ 的数据满足 $n\\leq  8\\times 10^4$，$m\\leq 10^6$，$k\\leq 2$。\n\n对于 $80\\%$ 的数据满足 $n\\leq  8\\times 10^4$，$m\\leq 10^6$，$k\\leq 4$。\n\n对于 $100\\%$ 的数据满足 $2\\leq n\\leq 8\\times 10^4$，$1\\leq m\\leq 10^6$，$2\\leq k\\leq 7$，$1\\leq w\\leq100$。"}],"translated_statement":null,"sample_group":[["9 21 3\n1 2 1\n2 3 1\n3 4 1\n4 5 1\n5 6 1\n6 7 1\n7 8 1\n8 9 1\n1 3 1\n2 4 1\n3 5 1\n4 6 1\n5 7 1\n6 8 1\n7 9 1\n1 4 1\n2 5 1\n3 6 1\n4 7 1\n5 8 1\n6 9 1","3"],["5 10 2\n3 5 73\n3 4 33\n3 5 84\n4 5 10\n3 4 15\n1 2 83\n1 3 8\n1 3 24\n5 5 15\n1 2 62","32"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}