说明

Funini Adventure 是一款非常受欢迎的游戏。在这款游戏中，你可以通过执行以下三种行动来培养 Funini：

• 行动 1：爬山以增强耐力
• 行动 2：参加编程竞赛
• 行动 3：学习新算法

你打算多次执行这些行动，但每次行动都有其代价。对于 $i = 1, 2, 3$，执行行动 $i$ 的代价定义如下：如果你已经执行了行动 $i$ 恰好 $x_i$ 次，那么本次的代价为 $a_i + b_i x_i$。

初始时，你执行每种行动的次数均为 $0$。请求出总共执行 $N$ 次行动所需的最小总代价。

输入格式

输入包含多个测试用例。

第一行包含一个整数 $T$（$1 \leq T \leq 100\,000$），表示测试用例的数量。

接下来是 $T$ 个测试用例。每个测试用例的格式如下：

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

对于每个测试用例，第一行包含一个整数 $N$（$1 \leq N \leq 10^6$），表示你需要执行行动的总次数。

接下来的 $3$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq 10^6$）。第 $i$ 行给出了行动 $i$ 的系数。

输出格式

对于每个测试用例，输出一行，包含一个整数——执行 $N$ 次行动的最小总代价。

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

20
166667166667000000

提示

在第一个测试用例中，你需要总共执行 $5$ 次行动。如果你按顺序执行行动 $1, 3, 3, 2, 1$，那么代价分别为 $1, 4, 7, 2$ 和 $6$，总和为 $20$。可以证明，没有任何行动序列能获得比 $20$ 更小的总代价，因此答案为 $20$。

翻译由 DeepSeek V3.2 完成