B - Make N 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 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 に対する答えを出力してください。

入力例 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

出力例 1

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 かかる。

Score : 500 points

Problem Statement

We have an integer P=0. Find the minimum total cost to make P=N by doing the following three kinds of operations any number of times in any order.

  • Increase P by 1, at a cost of X.
  • Increase P by A, at a cost of Y.
  • Increase P by B, at a cost of Z.

Solve each of the T test cases given to you.

Constraints

  • 1 \le T \le 100
  • 1 \le N,A,B,X,Y,Z \le 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Each test case is in the following format:

N\ A\ B\ X\ Y\ Z

Output

Print T lines, the i-th of which should contain the answer to \mathrm{case}_i.

Sample Input 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

Sample Output 1

11
10
1
139
436604

In the first test case, below is one way to make P=10 at the cost of 11, which is optimal.

  • Increase P by 3, making P=3, at a cost of 3.
  • Increase P by 1, making P=4, at a cost of 2.
  • Increase P by 3, making P=7, at a cost of 3.
  • Increase P by 3, making P=10, at a cost of 3.