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: Find the minimum cost you need to pay to have the n -th Pok émon stand in the arena. 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 cdot 10^5 , 1 <= m <= 2 cdot 10^5 , 2 <= q n cdot m <= q 4 cdot 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 cdot m over all test cases does not exceed 4 cdot 10^5 . For each test case, output the minimum cost to make the n -th Pok émon stand in the arena. 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 ge 2=a_{1,1} , the 3 -r