众所周知,航空公司“麻烦”经常丢失行李,有关记者决定计算出最多可能无法归还给旅客的行李件数。
航空公司“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$$$ 的每个天数中未找到行李的最大数量。
示例
输入复制
25 31 1 1 1 10 0 1 0 00 1 0 0 11 0 0 1 00 1 0 0 09 0 9 9 90 1 0 0 00 0 0 0 09 0 9 0 00 0 0 0 03 10 100000000 50 100000000 50 100000000 50 100000000 5
输出复制
5 4 2 100000005
注意
在第一个测试用例中:
- 第一天,所有 $$$5$$$ 件行李可能无法找到,因为丢失的行李可以通过各个机场的航班寄送。
- 第二天上午,第$$$2$$$机场的行李不得超过$$$3$$$件,第$$$5$$$机场的行李不得超过$$$2$$$件,其他机场不得有行李。来自 $$$5$$$ 机场的所有行李均可留在那里。在 $$$2$$$-nd 机场,飞往邻近机场的航班最多可运送 $$$2$$$ 件行李。因此,至少会找到 $$$1$$$ 件行李。
- 到第三天结束时,丢失的行李可能只会出现在 $$$1$$$-st 和 $$$2$$$-nd 机场。每件行李不能超过一件,这意味着总共最多有 $$$2$$$ 件行李未被找到。
找到的行李标记为绿色。 在第二个测试案例中,所有行李都可以留在原来的机场,检查不会发现任何丢失的行李箱。因此,答案是$$$10^9 + 5$$$。