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

Вы находитесь на дуэльной арене. Вы также владеете $$$n$$$ покемонами. Изначально на арене находится только $$$1$$$-й покемон.

Каждый покемон имеет $$$m$$$ характеристик. Значение $$$j$$$-й характеристики у $$$i$$$-го покемона равно $$$a_{i,j}$$$. Также у каждого покемона есть стоимость его вызова: цена $$$i$$$-го покемона равна $$$c_i$$$.

Вы хотите добиться того, чтобы на арене находился $$$n$$$-й покемон. Для этого вы можете выполнять операции двух типов любое количество раз в любом порядке:

  • Выбрать три целых числа $$$i$$$, $$$j$$$, $$$k$$$ ($$$1 \le i \le n$$$, $$$1 \le j \le m$$$, $$$k > 0$$$) и навсегда увеличить $$$a_{i,j}$$$ на $$$k$$$. Стоимость такой операции равна $$$k$$$.
  • Выбрать два числа $$$i$$$, $$$j$$$ ($$$1 \le i \le n$$$, $$$1 \le j \le m$$$) и вызвать $$$i$$$-го покемона, который бросит вызов текущему покемону на арене по $$$j$$$-й характеристике. При этом $$$i$$$-й покемон победит, если $$$a_{i,j}$$$ не меньше, чем $$$j$$$-я характеристика текущего покемона на арене (иначе он проиграет). После дуэли на арене остаётся только её победитель. Стоимость такой операции равна $$$c_i$$$.

Найдите наименьшую суммарную стоимость операций, необходимых для того, чтобы на арене оказался $$$n$$$-й покемон.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 4 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$, $$$2 \leq n \cdot m \leq 4 \cdot 10^5$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 10^9$$$).

Далее, $$$i$$$-я из следующих $$$n$$$ строк содержит $$$m$$$ целых чисел $$$a_{i,1}, a_{i,2}, \ldots, a_{i,m}$$$ ($$$1 \le a_{i,j} \le 10^9$$$).

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

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

Для каждого набора входных данных выведите минимальную суммарную стоимость операций, чтобы на арене оказался $$$n$$$-й покемон.

Пример
Входные данные
4
3 3
2 3 1
2 9 9
6 1 7
1 2 1
3 3
2 3 1
9 9 9
6 1 7
1 2 1
4 2
2 8 3 5
18 24
17 10
1 10
1 1
6 3
21412674 3212925 172015806 250849370 306960171 333018900
950000001 950000001 950000001
821757276 783362401 760000001
570000001 700246226 600757652
380000001 423513575 474035234
315201473 300580025 287023445
1 1 1
Выходные данные
2
6
17
1224474550
Примечание

В первом наборе входных данных массив значений характеристик $$$1$$$-го покемона (который изначально расположен на арене) есть $$$[2,9,9]$$$.

На первой операции можно выбрать $$$i=3$$$, $$$j=1$$$, $$$k=1$$$ и увеличить $$$a_{3,1}$$$ на $$$1$$$ навсегда. Теперь массив значений характеристик $$$3$$$-го покемона станет равен $$$[2,2,1]$$$. Стоимость этой операции равна $$$k = 1$$$.

На второй операции можно выбрать $$$i=3$$$, $$$j=1$$$ и вызвать $$$3$$$-го покемона, который сразится с текущим покемоном на арене по $$$1$$$-й характеристике. Поскольку $$$a_{i,j}=a_{3,1}=2 \ge 2=a_{1,1}$$$, $$$3$$$-й покемон победит. Стоимость этой операции равна $$$c_3 = 1$$$.

Таким образом, $$$3$$$-й покемон находится на арене, а суммарная стоимость операций равна $$$2$$$. Можно показать, что меньше $$$2$$$ ответ получить нельзя.

Во втором наборе входных данных массив значений характеристик $$$1$$$-го покемона есть $$$[9,9,9]$$$.

На первой операции можно выбрать $$$i=2$$$, $$$j=3$$$, $$$k=2$$$ и увеличить $$$a_{2,3}$$$ на $$$2$$$ навсегда. Теперь массив значений характеристик $$$2$$$-го покемона есть $$$[6,1,9]$$$. Стоимость этой операции равна $$$k = 2$$$.

На второй операции можно выбрать $$$i=2$$$, $$$j=3$$$ и вызвать $$$2$$$-го покемона, который сразится с текущим покемоном на арене по $$$3$$$-й характеристике. Поскольку $$$a_{i,j}=a_{2,3}=9 \ge 9=a_{1,3}$$$, $$$2$$$-й покемон победит. Стоимость этой операции равна $$$c_2 = 3$$$.

На третьей операции можно выбрать $$$i=3$$$, $$$j=2$$$ и вызвать $$$3$$$-го покемона, который сразится с текущим покемоном на арене по $$$2$$$-й характеристике. Поскольку $$$a_{i,j}=a_{1,2}=2 \ge 1=a_{2,2}$$$, $$$3$$$-й покемон победит. Стоимость этой операции равна $$$c_3 = 1$$$.

Таким образом, $$$3$$$-й покемон находится на арене, а суммарная стоимость операций равна $$$6$$$. Можно показать, что меньше $$$6$$$ ответ получить нельзя.