Funini Adventure is a very popular game. In this game, you can raise Funini by performing the following three actions.
Action 1: Climb a mountain to build stamina
Action 2: Participate in a programming contest
Action 3: Learn a new algorithm
You want to perform these actions several times, but each action has a cost. For , the cost of performing Action is defined as follows: if you have already performed Action exactly times, then the cost is .
Initially, you have performed each action 0 times. Find the minimum total cost required to perform actions in total.
输入格式
The input consists of multiple test cases.
The first line contains an integer (), representing the number of test cases.
test cases follow. Each test case is given in the following format.
For each test case, the first line contains an integer (), representing the number of actions you should perform.
The following 3 lines each contain two integers and (). The -th of these lines gives the coefficients for Action .
输出格式
For each test case, output a line containing a single integer – the minimum total cost to perform actions.
In the first test case, you need to perform the three actions a total of 5 times. If you perform Actions in this order, then the costs are and , for a total of . Since it can be shown that no sequence achieves a total cost less than , the answer is .
