← 返回题目列表

Codeforces · 362/E

E. Petya 和管道

中文机器翻译题面 查看原题

一个小男孩 Petya 梦想长大并成为 Berland 水管工主管。他正在思考自己未来要解决的问题。不幸的是,Petya 经验太少,所以你要为 Petya 解决其中一个他最感兴趣的问题。

Berland首都有n个水箱,编号从1到n。这些储罐通过单向管道以某种方式连接。任意一对水箱每个方向最多由一根管道连接。每个管道都有严格的正整数宽度。宽度决定了该管道每单位时间可以输送的水的升数。水从主水箱(编号为1)流向城市。水必须经过一定的管道到达带有清洗系统的污水箱(其数量为n)。

Petya 希望将某些管道子集的宽度总共最多增加 k 个单位,以便每个管道的宽度保持整数。帮助他确定这样的操作完成后,单位时间内可以从主水箱输送到下水道水箱的最大水量。

输入

第一行包含两个空格分隔的整数 n 和 k (2 ≤ n ≤ 50, 0 ≤ k ≤ 1000)。然后n行,每行包含n个整数,用单个空格分隔。第 i + 1 行和第 j 列包含数字 cij — 从储罐 i 到储罐 j 的管道宽度(0 ≤ cij ≤ 106,cii = 0)。如果 cij = 0,则从储罐 i 到储罐 j 之间没有管道。

输出

打印一个整数——单位时间内可以从主水箱传输到下水道水箱的最大水量。

示例

输入 #1

5 7
0 1 0 2 0
0 0 4 10 0
0 0 0 0 5
0 0 0 0 10
0 0 0 0 0

输出 #1

10

输入 #2

5 10
0 1 0 0 0
0 0 2 0 0
0 0 0 3 0
0 0 0 0 4
100 0 0 0 0

输出 #2

5

注意

在第一个测试中,Petya 可以将从第一个水箱到第二个水箱的管道宽度增加 7 个单位。

在第二次测试中,Petya 可以将第 1 个到第 2 个水箱的管道宽度增加 4 个单位,从第 2 个到第 3 个水箱增加 3 个单位,从第 3 个到第 4 个水箱增加 2 个单位,从第 4 个到第 5 个水箱增加 1 个单位。