← 返回题目列表

Codeforces · 2097/F

F. 行李丢失

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

众所周知,航空公司“麻烦”经常丢失行李,有关记者决定计算出最多可能无法归还给旅客的行李件数。

航空公司“Trouble”在 $$$n$$$ 机场之间运营航班,编号从 $$$1$$$ 到 $$$n$$$。记者们的实验将持续 $$$m$$$ 天。据了解,实验第一天前午夜,第$$$j$$$机场有$$$s_j$$$件行李丢失。在第 $$$i$$$ 天,发生以下情况:

  • 早上, $$$2n$$$航班同时起飞,其中包括$$$n$$$航班 第一种类型 和 $$$n$$$ 航班 第二种类型.
    • 第一类第$$$j$$$航班从机场$$$j$$$飞往机场$$$(((j-2) \bmod n )+ 1)$$$(前一个机场,第一个机场为最后一个机场),可携带不超过$$$a_{i,j}$$$的丢失行李件数。
    • 第二类第$$$j$$$航班从机场$$$j$$$飞往机场$$$((j \bmod n) + 1)$$$(下一个机场,最后一个机场为第一个机场),最多可携带$$$c_{i,j}$$$件丢失行李。
  • 下午,在机场进行丢失行李检查。若当日航班起飞后,第$$$j$$$机场还剩余$$$x$$$件行李,且$$$x \ge b_{i, j}$$$,则至少找到$$$x - b_{i, j}$$$件行李,且 不再丢失.
  • 晚上,所有$$$2n$$$航班结束,当天运输的丢失行李到达相应机场。

对于从 $$$1$$$ 到 $$$m$$$ 的每 $$$k$$$,记者想知道可能丢失的行李件数的最大数量 未找到 在前 $$$k$$$ 天的检查期间。请注意,对于每个 $$$k$$$,这些值是独立计算的。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$3 \le n \le 12$$$, $$$1 \le m \le 2000$$$) - 机场数量和实验天数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$s_1, s_2, \ldots, s_n$$$ ($$$0 \le s_i \le 10^8$$$) – 每个机场丢失行李的初始件数。

接下来,按顺序对 $$$m$$$ 日的每一天进行描述。

第 $$$i$$$ 天的描述第一行包含 $$$n$$$ 整数 $$$a_{i,1}, a_{i,2}, \ldots, a_{i,n}$$$ ($$$0 \le a_{i, j} \le 10^8$$$) — 可运送到前一机场的丢失行李的最大件数对于每个机场。

第 $$$i$$$ 天的描述第二行包含 $$$n$$$ 整数 $$$b_{i,1}, \ldots, b_{i,n}$$$ ($$$0 \le b_{i, j} \le 10^8$$$) — 在第 $$$i$$$ 天找到的丢失行李的最少件数每个机场。

第 $$$i$$$ 天的描述第三行包含 $$$n$$$ 整数 $$$c_{i,1}, \ldots, c_{i,n}$$$ ($$$0 \le c_{i, j} \le 10^8$$$) – 每个机场可以运送到下一个机场的最大丢失行李件数。

保证所有测试用例的 $$$m$$$ 总和不超过 $$$2000$$$。

输出

对于每个测试用例,输出 $$$m$$$ 整数 - 从 $$$1$$$ 到 $$$m$$$ 的每个天数中未找到行李的最大数量。

示例

输入
复制

2
5 3
1 1 1 1 1
0 0 1 0 0
0 1 0 0 1
1 0 0 1 0
0 1 0 0 0
9 0 9 9 9
0 1 0 0 0
0 0 0 0 0
9 0 9 0 0
0 0 0 0 0
3 1
0 100000000 5
0 100000000 5
0 100000000 5
0 100000000 5

输出
复制

5
4
2
100000005

注意

在第一个测试用例中:

  • 第一天,所有 $$$5$$$ 件行李可能无法找到,因为丢失的行李可以通过各个机场的航班寄送。
  • 第二天上午,第$$$2$$$机场的行李不得超过$$$3$$$件,第$$$5$$$机场的行李不得超过$$$2$$$件,其他机场不得有行李。来自 $$$5$$$ 机场的所有行李均可留在那里。在 $$$2$$$-nd 机场,飞往邻近机场的航班最多可运送 $$$2$$$ 件行李。因此,至少会找到 $$$1$$$ 件行李。
  • 到第三天结束时,丢失的行李可能只会出现在 $$$1$$$-st 和 $$$2$$$-nd 机场。每件行李不能超过一件,这意味着总共最多有 $$$2$$$ 件行李未被找到。
找到的行李标记为绿色。

在第二个测试案例中,所有行李都可以留在原来的机场,检查不会发现任何丢失的行李箱。因此,答案是$$$10^9 + 5$$$。