题目描述

耳廓狐亚砜最近沉迷于《异界失控》这款围绕其独创的横版一维战场系统构建的 Roguelite 战术回合制游戏。当他在这个特殊的战场上利用关键的站位机制与合理的技能点分配，操控自己的战士小队击溃敌方、所向披靡时，他遇到了又一个突发事件——陨石。

针对本题，我们不妨让这个突发事件比原版游戏还要极端。

考虑一个由 $1$ 到 $n$ 依次编号的 $n$ 个地块组成的线状战场。初始战场上没有任何陨石，只有若干角色被放置在某些地块上。亚砜的目标是确保所有角色在 $m$ 轮陨石灾难中无一伤亡。

第 $i$ 轮（$i=1,2,\ldots,m$）开始时，对于每个 $j=1,2,\ldots,n$，恰好有 $a_{i,j}$ 颗陨石降落在第 $j$ 个地块上，并与该地块原有的陨石叠加。

在陨石落下的阶段严禁移动角色。因此，任何站在本轮有陨石降落的地块上的角色都会立即死亡。

本轮所有陨石落地后，进入行动阶段。此时，亚砜可以将任意存活角色移动到相邻地块；在本轮结束前，每个角色都可以进行任意多次（也可以是零次）这样的移动。

现有的陨石会阻止角色进入其所在的地块。在角色进入这样的地块之前，亚砜必须摧毁该地块上的全部陨石；每摧毁一颗陨石需要花费 $1$ 点数。

请计算确保所有角色在全部 $m$ 轮陨石灾难中存活所需的最少点数；若无法做到，输出 $-1$。

输入格式

第一行包含一个整数 $T$，表示测试数据组数。

对于每组测试数据：

• 第一行包含两个整数 $n,m$，分别表示地块数量和灾难轮数；

• 第二行包含 $n$ 个整数 $c_1,c_2,\ldots,c_n$。当且仅当 $c_i=1$ 时，第 $i$ 个地块上初始有一个角色；

• 接下来 $m$ 行，第 $i$ 行包含 $n$ 个整数

  $$a_{i,1},a_{i,2},\ldots,a_{i,n},$$

  其中 $a_{i,j}$ 表示第 $i$ 轮开始时降落在第 $j$ 个地块上的陨石数量。

保证至少存在一个角色。

输出格式

对于每组测试数据：

• 若无法确保所有角色存活，输出 -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

数据范围

对于所有数据：

所有测试数据的 $n\times m$ 之和不超过 $10^6$。

提示

评测时将开启合理的子任务依赖。