题目描述

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 $i = 1, 2, 3$, the cost of performing Action $i$ is defined as follows: if you have already performed Action $i$ exactly $x_i$ times, then the cost is $a_i + b_i x_i$.

Initially, you have performed each action 0 times. Find the minimum total cost required to perform $N$ actions in total.

输入格式

The input consists of multiple test cases.

The first line contains an integer $T$ ($1 \leq T \leq 100\,000$), representing the number of test cases.

$T$ test cases follow. Each test case is given in the following format.

$$\begin{aligned} & N \\ & a_1 \ b_1 \\ & a_2 \ b_2 \\ & a_3 \ b_3 \end{aligned} $$

For each test case, the first line contains an integer $N$ ($1 \leq N \leq 10^6$), representing the number of actions you should perform.

The following 3 lines each contain two integers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq 10^6$). The $i$-th of these lines gives the coefficients for Action $i$.

输出格式

For each test case, output a line containing a single integer – the minimum total cost to perform $N$ actions.

2
5
1 5
2 10
4 3
1000000
1000000 1000000
1000000 1000000
1000000 1000000

20
166667166667000000

提示

In the first test case, you need to perform the three actions a total of 5 times. If you perform Actions $1, 3, 3, 2, 1$ in this order, then the costs are $1, 4, 7, 2,$ and $6$, for a total of $20$. Since it can be shown that no sequence achieves a total cost less than $20$, the answer is $20$.