P15779 [JAG 2025 Summer Camp #3] Funini Adventure

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$ 次行动的最小总代价。

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