题目描述

有一个整数 $P=0$。你可以任意次数选择以下三种操作中的任意一种，通过这些操作使得 $P=N$，请你求出总花费的最小值。

• 使 $P$ 增加 $1$。该操作的花费为 $X$。
• 使 $P$ 增加 $A$。该操作的花费为 $Y$。
• 使 $P$ 增加 $B$。该操作的花费为 $Z$。

给定 $T$ 组测试数据，请分别输出每组的答案。

输入格式

输入以以下格式从标准输入读入。

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每组测试数据格式如下：

$N\ A\ B\ X\ Y\ Z$

输出格式

请输出 $T$ 行，第 $i$ 行输出第 $i$ 组测试数据的答案。

样例 1

输入

5
10 3 5 2 3 6
10 3 5 1 1000000000 1000000000
139 2 139 1 1 1
139 1 1 1 1 1
139 7 10 3845 26982 30923

输出

11
10
1
139
436604

说明/提示

数据范围

• $1 \leq T \leq 100$
• $1 \leq N, A, B, X, Y, Z \leq 10^9$
• 所有输入均为整数。

样例解释 1

对于第 $1$ 组测试数据，例如可以按如下方式以总花费 $11$ 达到 $P=10$，且这是最优解。

• 使 $P$ 增加 $3$，此时 $P=3$，花费 $3$。
• 使 $P$ 增加 $1$，此时 $P=4$，花费 $2$。
• 使 $P$ 增加 $3$，此时 $P=7$，花费 $3$。
• 使 $P$ 增加 $3$，此时 $P=10$，花费 $3$。

由 ChatGPT 4.1 翻译