{"raw_statement":[{"iden":"statement","content":"给定 $n$ 个点，$m$  条边，给定每条边的容量和单位流量需要支付的费用，求点 $1$ 到点 $n$ 的最大流以及此时需要的最小费用。\n\n**注意，图可能存在重边。**\n"},{"iden":"input","content":"第一行两个整数 $n$、$m$，表示有 $n$ 个点 $m$ 条边。\n\n从第二行开始的之后 $m$ 行，每行四个整数 $s_i$、$t_i$、$c_i$、$w_i$ 表示一条从 $s_i$ 到 $t_i$ 的边，容量为 $c_i$，单位流量需要支付的费用为 $w_i$。\n"},{"iden":"output","content":"输出一行两个整数，表示最大流和最小费用。"},{"iden":"note","content":"对于所有数据，保证 $1 \\le n \\le 400$，$0 \\le m \\le 15000$，$0 \\le w_i \\le 2 ^ {31} - 1$，保证答案在 32 位有符号整数范围内。\n\n本题数据较弱，不存在最小费用最大流的极限情况。\n\n实现时，若使用 Bellman-Ford 算法可以考虑如下优化：若在某次迭代中所有 $\\pi(i)$ 均保持不变，则不继续迭代。\n"}],"translated_statement":null,"sample_group":[["8 23\n2 3 2147483647 1\n1 3 1 1\n2 4 2147483647 2\n1 4 1 2\n2 8 2 0\n3 5 2147483647 3\n1 5 1 3\n3 6 2147483647 4\n1 6 1 4\n3 8 2 0\n3 2 2147483647 0\n4 6 2147483647 5\n1 6 1 5\n4 7 2147483647 6\n1 7 1 6\n4 8 2 0\n4 2 2147483647 0\n5 8 0 0\n5 2 2147483647 0\n6 8 0 0\n6 2 2147483647 0\n7 8 0 0\n7 2 2147483647 0\n","6 24"],["10 30\n1 9 23 2\n9 6 29 8\n2 8 22 20\n7 3 10 16\n3 10 18 19\n1 2 18 29\n9 8 18 15\n4 10 5 12\n7 5 30 12\n7 8 29 7\n9 5 20 26\n9 4 15 5\n9 10 21 6\n9 8 15 8\n3 4 10 7\n3 10 2 5\n3 10 26 6\n9 3 11 14\n6 4 11 7\n2 5 1 20\n9 5 1 1\n6 10 10 17\n8 10 29 5\n9 4 10 22\n5 10 3 14\n8 5 16 25\n7 10 21 25\n1 9 11 16\n1 2 14 15\n7 9 30 25\n","57 1594"],["10 30\n7 4 7 19\n9 10 6 12\n6 4 13 2\n3 5 18 21\n8 10 12 4\n9 4 11 1\n2 5 23 2\n2 10 2 7\n6 5 13 22\n8 5 2 10\n5 7 12 14\n6 5 22 17\n5 10 27 23\n1 6 1 21\n2 7 30 16\n4 5 17 12\n1 3 27 25\n2 7 19 27\n1 9 18 25\n4 7 30 28\n6 10 20 16\n1 2 16 21\n3 5 26 2\n1 9 1 4\n1 2 6 7\n2 9 25 28\n3 8 11 2\n2 3 9 14\n9 4 16 2\n1 7 3 15\n","47 1821"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}