You are at a dueling arena. You also possess Pokémons. Initially, only the -st Pokémon is standing in the arena.
Each Pokémon has attributes. The -th attribute of the -th Pokémon is . Each Pokémon also has a cost to be hired: the -th Pokémon's cost is .
You want to have the -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 , , ( , , ), increase by permanently. The cost of this operation is .
Choose two integers , ( , ) and hire the -th Pokémon to duel with the current Pokémon in the arena based on the -th attribute. The -th Pokémon will win if is greater than or equal to the -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 .
Find the minimum cost you need to pay to have the -th Pokémon stand in the arena.
输入格式
Each test contains multiple test cases. The first line contains the number of test cases ( ). The description of the test cases follows.
The first line of each test case contains two integers and ( , , ).
The second line of each test case contains integers ( ).
The -th of the following lines contains integers ( ).
It is guaranteed that the sum of over all test cases does not exceed .
输出格式
For each test case, output the minimum cost to make the -th Pokémon stand in the arena.
In the first test case, the attribute array of the -st Pokémon (which is standing in the arena initially) is .
In the first operation, you can choose , , , and increase by permanently. Now the attribute array of the -rd Pokémon is . The cost of this operation is .
In the second operation, you can choose , , and hire the -rd Pokémon to duel with the current Pokémon in the arena based on the -st attribute. Since , the -rd Pokémon will win. The cost of this operation is .
Thus, we have made the -rd Pokémon stand in the arena within the cost of . It can be proven that is minimum possible.
In the second test case, the attribute array of the -st Pokémon in the arena is .
In the first operation, you can choose , , , and increase by permanently. Now the attribute array of the -nd Pokémon is . The cost of this operation is .
In the second operation, you can choose , , and hire the -nd Pokémon to duel with the current Pokémon in the arena based on the -rd attribute. Since , the -nd Pokémon will win. The cost of this operation is .
In the third operation, you can choose , , and hire the -rd Pokémon to duel with the current Pokémon in the arena based on the -nd attribute. Since , the -rd Pokémon can win. The cost of this operation is .
Thus, we have made the -rd Pokémon stand in the arena within the cost of . It can be proven that is minimum possible.