#P18224. Crisis Event: Meteorite

Crisis Event: Meteorite

Crisis Event: Meteorite

Sulfox 最近迷上了采用一维战场的回合制策略游戏 Anomaly Collapse。新的危机事件“陨石”来临了,你需要帮助他让所有角色活过灾难。

战场由从左到右编号为 1,2,…,n1,2,\ldots,n 的 nn 个格子组成。最初,所有格子上都没有陨石,一些格子上各有一个角色。整个灾难持续 mm 轮。

第 ii 轮依次进行以下两个阶段:

  1. 落石阶段。 对于每个格子 jj,有 ai,ja_{i,j} 块陨石落在该格子上,与尚未清除的陨石累积。这个阶段角色不能移动。若某个角色站的格子有新的陨石落下,该角色会立即被砸死。
  2. 行动阶段。 可以将任意存活角色移动到相邻格子。每个角色在本阶段可以移动任意多次,也可以不移动。但是,格子上现有的陨石会阻止角色进入。在角色进入这个格子之前,必须花费每块陨石 11 点的费用,将这个格子上现有的陨石全部清除。

原题落石示意:不要让角色站在即将落石的格子上

费用是所有角色共享的:同一批陨石清除后,其他角色经过时不需要再次为这批陨石付费;之后落下的新陨石仍会累积。角色之间不阻挡移动,可以在同一格会合,也可以再次分开。

求让所有角色活过全部 mm 轮所需的最少总费用。若无法做到,输出 −1-1。

输入格式

第一行包含一个整数 TT,表示测试用例数。

每个测试用例:

  • 第一行包含两个整数 n,mn,m,分别表示格子数和轮数。
  • 第二行包含 nn 个整数 c1,c2,…,cnc_1,c_2,\ldots,c_n。当且仅当 cj=1c_j=1 时,第 jj 个格子最初有一个角色。
  • 接下来 mm 行,每行包含 nn 个整数。第 ii 行第 jj 个数为 ai,ja_{i,j},表示第 ii 轮开始时落在第 jj 个格子上的陨石数。

数据范围:

$$1\le T\le10^4,\qquad 1\le n,m\le10^6,\qquad 1\le nm\le10^6;$$$$c_j\in\{0,1\},\qquad \sum_{j=1}^n c_j\ge1,\qquad 0\le a_{i,j}\le1000.$$

所有测试用例的 nmnm 之和不超过 10610^6。

输出格式

对于每个测试用例输出一行:若不可能让所有角色存活,输出 −1-1;否则输出所需的最少总费用。

样例

2
3 4
1 0 1
0 1 0
2 0 0
0 0 3
4 5 0
1 1
1
1000
4
-1

样例说明

第一个测试用例可以这样行动:

  • 第一轮落石后,花费 11 点清除第 22 格的陨石,让第 11 格的角色走到第 33 格,与另一个角色会合。
  • 第二轮两个角色留在第 33 格。
  • 第二轮行动阶段,让两个角色回到第 22 格,以躲过第三轮落在第 33 格的陨石。
  • 第三轮行动阶段,花费 33 点清除第 33 格的陨石,两个角色回到第 33 格,从而躲过第四轮的落石。

总费用为 1+3=41+3=4。第二个测试用例的角色在第一轮落石时立即死亡。