P15779 [JAG 2025 Summer Camp #3] Funini Adventure

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.

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$.