#P18224. Crisis Event: Meteorite
Crisis Event: Meteorite
Crisis Event: Meteorite
Sulfox 最近迷上了采用一维战场的回合制策略游戏 Anomaly Collapse。新的危机事件“陨石”来临了,你需要帮助他让所有角色活过灾难。
战场由从左到右编号为 的 个格子组成。最初,所有格子上都没有陨石,一些格子上各有一个角色。整个灾难持续 轮。
第 轮依次进行以下两个阶段:
- 落石阶段。 对于每个格子 ,有 块陨石落在该格子上,与尚未清除的陨石累积。这个阶段角色不能移动。若某个角色站的格子有新的陨石落下,该角色会立即被砸死。
- 行动阶段。 可以将任意存活角色移动到相邻格子。每个角色在本阶段可以移动任意多次,也可以不移动。但是,格子上现有的陨石会阻止角色进入。在角色进入这个格子之前,必须花费每块陨石 点的费用,将这个格子上现有的陨石全部清除。

费用是所有角色共享的:同一批陨石清除后,其他角色经过时不需要再次为这批陨石付费;之后落下的新陨石仍会累积。角色之间不阻挡移动,可以在同一格会合,也可以再次分开。
求让所有角色活过全部 轮所需的最少总费用。若无法做到,输出 。
输入格式
第一行包含一个整数 ,表示测试用例数。
每个测试用例:
- 第一行包含两个整数 ,分别表示格子数和轮数。
- 第二行包含 个整数 。当且仅当 时,第 个格子最初有一个角色。
- 接下来 行,每行包含 个整数。第 行第 个数为 ,表示第 轮开始时落在第 个格子上的陨石数。
数据范围:
$$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.$$所有测试用例的 之和不超过 。
输出格式
对于每个测试用例输出一行:若不可能让所有角色存活,输出 ;否则输出所需的最少总费用。
样例
2
3 4
1 0 1
0 1 0
2 0 0
0 0 3
4 5 0
1 1
1
1000
4
-1
样例说明
第一个测试用例可以这样行动:
- 第一轮落石后,花费 点清除第 格的陨石,让第 格的角色走到第 格,与另一个角色会合。
- 第二轮两个角色留在第 格。
- 第二轮行动阶段,让两个角色回到第 格,以躲过第三轮落在第 格的陨石。
- 第三轮行动阶段,花费 点清除第 格的陨石,两个角色回到第 格,从而躲过第四轮的落石。
总费用为 。第二个测试用例的角色在第一轮落石时立即死亡。