E. Pokémon Arena

内存限制
512 MiB
时间限制
2000 ms
标准输入输出
题目类型
传统
评测方式
无测试数据
上传者 admin
题目来源 luogu

题目描述

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.

样例

输入 #1

4
3 3
2 3 1
2 9 9
6 1 7
1 2 1
3 3
2 3 1
9 9 9
6 1 7
1 2 1
4 2
2 8 3 5
18 24
17 10
1 10
1 1
6 3
21412674 3212925 172015806 250849370 306960171 333018900
950000001 950000001 950000001
821757276 783362401 760000001
570000001 700246226 600757652
380000001 423513575 474035234
315201473 300580025 287023445
1 1 1

输出 #1

2
6
17
1224474550

数据范围与提示

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.