CF362E Petya and Pipes

小男孩 Petya 梦想长大后成为 Berland 的首席水管工。他正在思考将来需要解决的问题。不幸的是，Petya 现在还太缺乏经验，于是你需要帮 Petya 解决他最感兴趣的一个问题。 Berland 的首都拥有 $n$ 个水箱，编号从 $1$ 到 $n$。这些水箱通过一些单向管道相连。任意一对水箱之间每个方向最多只会由一根管道连接。每根管道都有一个严格正整数宽度。宽度决定了该管道每单位时间能运输的水量（升数）。水从主水箱（编号为 $1$）流向城市，必须经过某条管道路径最终流到带有净化系统的下水道水箱（编号为 $n$）。 Petya 想将部分管道的宽度增加，总共最多增加 $k$ 个单位，每根管道的宽度必须保持整数。请帮助他确定操作完成后主水箱到下水道水箱每单位时间能传输的最大水量。

第一行包含两个用空格分隔的整数 $n$ 和 $k$（$2 \leq n \leq 50$，$0 \leq k \leq 1000$）。接下来有 $n$ 行，每行包含 $n$ 个用单个空格分隔的整数。第 $i+1$ 行第 $j$ 列为 $c_{ij}$，表示从水箱 $i$ 到水箱 $j$ 的管道宽度（$0 \leq c_{ij} \leq 10^6,\ c_{ii} = 0$）。如果 $c_{ij} = 0$，表示没有从 $i$ 到 $j$ 的管道。

输出一个整数，表示操作完成后主水箱到下水道水箱每单位时间能传输的最大水量。

在第一个测试中，Petya 可以将从第 $1$ 个水箱到第 $2$ 个水箱的管道宽度增加 $7$ 单位。 在第二个测试中，Petya 可以将从第 $1$ 个水箱到第 $2$ 个水箱的管道宽度增加 $4$ 单位，从第 $2$ 个水箱到第 $3$ 个水箱的管道宽度增加 $3$ 单位，从第 $3$ 个水箱到第 $4$ 个水箱的管道宽度增加 $2$ 单位，从第 $4$ 个水箱到第 $5$ 个水箱的管道宽度增加 $1$ 单位。 由 ChatGPT 5 翻译