CF2097F.Lost Luggage

众所周知，航空公司"Trouble"经常丢失行李，为此关心的记者们决定计算可能无法归还给旅客的行李最大数量。

航空公司"Trouble"在编号从 $1$ 到 $n$ 的 $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$ 个航班结束，运输的遗失行李抵达对应机场。

对于每个 $k$ 从 $1$ 到 $m$，记者们想知道在前 $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$）——每个机场可以运输到前一个机场的遗失行李最大数量；
• 第二行包含 $n$ 个整数 $b_{i,1}, \ldots, b_{i,n}$（$0 \le b_{i, j} \le 10^8$）——第 $i$ 天每个机场将被找到的遗失行李最小数量；
• 第三行包含 $n$ 个整数 $c_{i,1}, \ldots, c_{i,n}$（$0 \le c_{i, j} \le 10^8$）——每个机场可以运输到后一个机场的遗失行李最大数量。

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

对于每个测试用例，输出 $m$ 个整数——分别对应前 $1$ 天到前 $m$ 天可能未被找到的遗失行李最大数量。

在第一个测试用例中：

• 第一天，所有 $5$ 件行李都可能未被找到，因为可以从每个机场发送航班运输遗失行李；
• 第二天早晨，第 $2$ 个机场最多可能有 $3$ 件行李，第 $5$ 个机场最多 $2$ 件，其他机场可能没有行李。所有行李可能仍留在第 $5$ 个机场。在第 $2$ 个机场，最多 $2$ 件行李可以被发送到相邻机场。因此，至少有 $1$ 件行李会被找到；
• 到第三天结束时，遗失行李可能只在第 $1$ 和第 $2$ 个机场。每个机场最多有 $1$ 件，意味着最多总共 $2$ 件行李未被找到。

在第二个测试用例中，所有行李可能留在原机场，检查不会找到任何遗失行李。因此答案是 $10^8 + 5$。

翻译由 DeepSeek V3 完成