配点 : $500$ 点

問題文

整数 $P=0$ があります。以下の $3$ 種類の操作を任意の回数選んで行うことで $P=N$ とするとき、コストの総和の最小値を求めてください。

• $P$ を $1$ 増やす。この操作はコストが $X$ かかる。
• $P$ を $A$ 増やす。この操作はコストが $Y$ かかる。
• $P$ を $B$ 増やす。この操作はコストが $Z$ かかる。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• $1 \le T \le 100$
• $1 \le N,A,B,X,Y,Z \le 10^9$
• 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられます。

$T$

$\mathrm{case}_1$

$\mathrm{case}_2$

$\vdots$

$\mathrm{case}_T$

各テストケースは以下の形式で与えられます。

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

出力

$T$ 行出力してください。$i$ 行目には、$\mathrm{case}_i$ に対する答えを出力してください。

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$ 個目のテストケースでは、例えば以下のようにするとコスト $11$ で $P=10$ とでき、これが最適です。

• $P$ を $3$ 増やす。$P=3$ となる。コストが $3$ かかる。
• $P$ を $1$ 増やす。$P=4$ となる。コストが $2$ かかる。
• $P$ を $3$ 増やす。$P=7$ となる。コストが $3$ かかる。
• $P$ を $3$ 増やす。$P=10$ となる。コストが $3$ かかる。