write a go solution for Description:
You are at a dueling arena. You also possess n Pokémons. Initially, only the 1-st Pokémon is standing in the arena.

Each Pokémon has m attributes. The j-th attribute of the i-th Pokémon is a_i,j. Each Pokémon also has a cost to be hired: the i-th Pokémon's cost is c_i.

You want to have the n-th Pokémon stand in the arena. To do that, you can perform the following two types of operations any number of times in any order:

- Choose three integers i, j, k (1<=i<=n, 1<=j<=m, k>0), increase a_i,j by k permanently. The cost of this operation is k.
- Choose two integers i, j (1<=i<=n, 1<=j<=m) and hire the i-th Pokémon to duel with the current Pokémon in the arena based on the j-th attribute. The i-th Pokémon will win if a_i,j is greater than or equal to the j-th attribute of the current Pokémon in the arena (otherwise, it will lose). After the duel, only the winner will stand in the arena. The cost of this operation is c_i.

Find the minimum cost you need to pay to have the n-th Pokémon stand in the arena.

Input Format:
Each test contains multiple test cases. The first line contains the number of test cases t (1<=t<=10^5). The description of the test cases follows.

The first line of each test case contains two integers n and m (2<=n<=4*10^5, 1<=m<=2*10^5, 2<=n*m<=4*10^5).

The second line of each test case contains n integers c_1,c_2,ldots,c_n (1<=c_i<=10^9).

The i-th of the following n lines contains m integers a_i,1,a_i,2,ldots,a_i,m (1<=a_i,j<=10^9).

It is guaranteed that the sum of n*m over all test cases does not exceed 4*10^5.

Output Format:
For each test case, output the minimum cost to make the n-th Pokémon stand in the arena.

Note:
In the first test case, the attribute array of the 1-st Pokémon (which is standing in the arena initially) is [2,9,9].

In the first operation, you can choose i=3, j=1, k=1, and increase a_3,1 by 1 permanently. Now the attribute array of the 3-rd Pokémon is [2,2,1]. The cost of this operation is k=1.

In the second operation, you can choose i=3, j=1, and hire the 3-rd Pokémon to duel with the current Pokémon in the arena based on the 1-st attribute. Since a_i,j=a_3,1=2>=2=a_1,1, the 3-rd Pokémon will win. The cost of this operation is c_3=1.

Thus, we have made the 3-rd Pokémon stand in the arena within the cost of 2. It can be proven that 2 is minimum possible.

In the second test case, the attribute array of the 1-st Pokémon in the arena is [9,9,9].

In the first operation, you can choose i=2, j=3, k=2, and increase a_2,3 by 2 permanently. Now the attribute array of the 2-nd Pokémon is [6,1,9]. The cost of this operation is k=2.

In the second operation, you can choose i=2, j=3, and hire the 2-nd Pokémon to duel with the current Pokémon in the arena based on the 3-rd attribute. Since a_i,j=a_2,3=9>=9=a_1,3, the 2-nd Pokémon will win. The cost of this operation is c_2=3.

In the third operation, you can choose i=3, j=2, and hire the 3-rd Pokémon to duel with the current Pokémon in the arena based on the 2-nd attribute. Since a_i,j=a_1,2=2>=1=a_2,2, the 3-rd Pokémon can win. The cost of this operation is c_3=1.

Thus, we have made the 3-rd Pokémon stand in the arena within the cost of 6. It can be proven that 6 is minimum possible.. Output only the code with no comments, explanation, or additional text.