Ayaan is managing a one-on-one arena match. There are n fighters . At the start, only the first fighter is standing in the arena.
Each fighter has m numeric traits. The trait j of fighter i is a[i][j]. Hiring a fighter i costs c[i].
Your goal is to make the n-th fighter end up standing in the arena. You may do these operations any number of times in any order:
- Pick a fighter i, a trait index j (1..m) and a positive integer k. Permanently increase a[i][j] by k. This operation costs exactly k.
- Pick a fighter i and a trait index j and hire fighter i to duel the current fighter in the arena using trait j. The hired fighter i wins and replaces the current arena fighter iff a[i][j] >= a[current][j]. Hiring fighter i costs c[i].
All trait values and costs are positive integers. It is always possible (by repeated upgrades and hires) to get the n-th fighter into the arena.
Find the minimum total cost needed to make the n-th fighter stand in the arena.
Constraints
2 ≤ n ≤ 4·10^5, 1 ≤ m ≤ 2·10^5, 2 ≤ n·m ≤ 4·10^5
1 ≤ ci ≤ 10^9
1 ≤ a[i][j] ≤ 10^9
Sum of n·m over all tests ≤ 4·10^5
Input Format
First line: integer t — number of test cases.
For each test case:
Line: integers n m.
Line: n integers c1 c2 ... cn.
Next n lines: each line has m integers — the trait values for fighter 1 through fighter n.
Output Format
For each test case print a single integer: the minimum total cost to have the n-th fighter stand in the arena.
Example 1
Input:
1
3 3
2 3 1
2 9 9
6 1 7
1 2 1
Output:
2
Explanation:
Explanation (story): Start: fighter 1 is in the arena with traits [2,9,9]. We raise the first trait of the target fighter named here as the 3rd fighter from 1 to 2 (cost 1), then hire that fighter (cost 1). Total cost 2.
Log In to solve the Question