C. Рискованная башня
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы играете в двухмерную игру «Дженга», представленную в виде сетки с $$$n$$$ строками и $$$m$$$ столбцами. $$$1$$$-я строка — верхний уровень башни, а $$$n$$$-я строка — нижний.

Каждый брусок, расположенный в строке $$$i$$$ и столбце $$$j$$$, имеет коэффициент дестабилизации $$$a_{i,j}$$$. Кроме того, каждая строка $$$i$$$ имеет начальный индекс устойчивости $$$v_i$$$.

Когда вы удаляете брусок, он полностью исключается из игры. Удаление бруска из $$$i$$$-го ряда наносит ущерб всем уровням, расположенным на этом уровне и выше. В частности, для каждого ряда $$$k$$$, такого что $$$1 \le k \le i$$$, его индекс устойчивости уменьшается на величину $$$a_{i,j}$$$.

Башня рушится, если выполняется любое из следующих условий:

  • Индекс устойчивости любого уровня падает до $$$0$$$ или ниже.
  • На любом уровне остаётся ровно $$$0$$$ брусков (даже если это самый верхний уровень).

Найдите минимальное количество брусков, которое необходимо удалить, чтобы башня рухнула.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных содержатся два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 10^6$$$) — количество строк и столбцов башни.

Во второй строке содержатся $$$n$$$ целых чисел $$$v_1, v_2, \ldots, v_n$$$ ($$$1 \le v_i \le 10^9$$$) — начальные индексы устойчивости каждого уровня сверху вниз.

Каждая из следующих $$$n$$$ строк содержит $$$m$$$ целых чисел. $$$j$$$-е целое число в $$$i$$$-й строке — это $$$a_{i, j}$$$ ($$$1 \le a_{i, j} \le 10^9$$$) — коэффициент дестабилизации бруска, расположенного в строке $$$i$$$ и столбце $$$j$$$.

Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальное количество кубиков, которое необходимо убрать, чтобы башня рухнула.

Пример
Входные данные
2
2 3
10 20
2 2 2
5 5 5
3 1
100 100 100
1
2
3
Выходные данные
2
1
Примечание

В первом наборе входных данных у нас башня размером $$$2 \times 3$$$. Начальные показатели устойчивости: $$$v_1 = 10$$$ и $$$v_2 = 20$$$. На верхнем уровне ($$$i=1$$$) находятся элементы с коэффициентами дестабилизации $$$2, 2, 2$$$. На нижнем уровне ($$$i=2$$$) находятся элементы $$$5, 5, 5$$$.

Если мы удалим два элемента с нижнего уровня, это нанесёт $$$5 + 5 = 10$$$ единиц урона уровню $$$2$$$ и $$$5 + 5 = 10$$$ единиц урона уровню $$$1$$$. Оставшаяся устойчивость уровня $$$1$$$ станет равной $$$10 - 10 = 0$$$. Поскольку его устойчивость упала до значения $$$\le 0$$$, башня рушится. Таким образом, минимальное количество элементов, которое мы должны удалить, равно $$$2$$$.

Во втором наборе входных данных $$$m = 1$$$. Согласно правилу, башня рушится, если на каком-либо уровне останется ровно $$$0$$$ блоков. Поскольку на каждом уровне изначально находится по $$$1$$$ блоку, удаление любого $$$1$$$ блока из башни мгновенно опустошит уровень и приведёт к обрушению. Следовательно, минимальное количество блоков, которое необходимо удалить, равно $$$1$$$.