CF1936C Pokémon Arena

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 \le i \le n $ , $ 1 \le j \le m $ , $ k > 0 $ ), increase $ a_{i,j} $ by $ k $ permanently. The cost of this operation is $ k $ . - Choose two integers $ i $ , $ j $ ( $ 1 \le i \le n $ , $ 1 \le j \le 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.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^5 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ 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 $ ). The second line of each test case contains $ n $ integers $ c_1, c_2, \ldots, c_n $ ( $ 1 \le c_i \le 10^9 $ ). The $ i $ -th of the following $ n $ lines contains $ m $ integers $ a_{i,1}, a_{i,2}, \ldots, a_{i,m} $ ( $ 1 \le a_{i,j} \le 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 $ -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 \ge 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 \ge 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.