Sulfox the fennec fox has recently become obsessed with Anomaly Collapse, a roguelite turn-based strategy game built around its innovative one-dimensional battlefield grid system. As he controls his squad of warriors to fight against enemies on the special battlefield, where positioning mechanisms and proper allocation of ability points are crucial for victory, he encounters another crisis event (a thoughtful "gift" from the game designers) as the factor introduced to escalate the challenge of the new chapter — Meteorite.
For this problem, let's push this crisis event to a more extreme version than the original game. Consider a linear battlefield consisting of $$$n$$$ grids numbered from $$$1$$$ to $$$n$$$ sequentially. Initially, the battlefield is clear of any meteorites, and several characters are positioned on certain grids. Sulfox's objective is to ensure the survival of all characters through $$$m$$$ rounds of the meteorite disaster.
At the beginning of the $$$i$$$-th round ($$$i = 1, 2, \ldots, m$$$), the fatal meteorite hazard unfolds: For each $$$j = 1, 2, \ldots, n$$$, exactly $$$a_{i,j}$$$ (possibly zero) meteorites descend upon the $$$j$$$-th grid, accumulating with any existing meteorites. Movement of characters is prohibited during this phase, which means any character unfortunate enough to be standing on a grid where meteorites descend will instantly be squashed into a pancake.
Do not let character stand on the grid where meteorites descend The action phase occurs after all meteorites for the $$$i$$$-th round have landed, during which Sulfox can move any surviving character to an adjacent grid, and this movement may be performed arbitrarily many times (possibly zero) for each character before this round ends. However, existing meteorites block characters from entering their occupied grids. Therefore, before a character can enter such a grid, Sulfox must spend $$$1$$$ point per meteorite on that grid to destroy them.
Please help Sulfox calculate the minimum number of points required to ensure the survival of all characters throughout the meteorite disaster, or report that it is an impossible mission to achieve the objective.
The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 10^4$$$), indicating the number of test cases. For each test case:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^6$$$, $$$1 \leq n \times m \leq 10^6$$$), indicating the number of grids and the number of rounds respectively.
The second line contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$c_i \in \{0, 1\}$$$). There is a character positioned on the $$$i$$$-th grid initially if and only if $$$c_i = 1$$$. It is guaranteed that there is at least one character in the game.
Then $$$m$$$ lines follow, the $$$i$$$-th of which contains $$$n$$$ integers $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}$$$ ($$$0 \leq a_{i, j} \leq 1\,000$$$), indicating that $$$a_{i, j}$$$ meteorites descend upon the $$$j$$$-th grid at the beginning of the $$$i$$$-th round.
It is guaranteed that the sum of $$$n \times m$$$ over all test cases does not exceed $$$10^6$$$.
For each test case, if it is impossible to ensure the survival of all characters, output $$$-1$$$ in one line. Otherwise, output an integer in one line, indicating the minimum number of points required.
23 41 0 10 1 02 0 00 0 34 5 01 111000
4 -1
