201391: [AtCoder]ARC139 B - Make N

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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$.

Input

题意翻译

给你一个数字 $N$ ,现在希望你用三个数字 $1,A,B$ 拼出 $N$ 但是使用一次 $1$ 要花掉 $X$ 元,用一次 $A$ 花掉$Y$ 元,用一次 $B$ 花掉 $Z$ 元 请你求出最小的花费 本题有多组数据。第一行输入数据组数 $T~(1\leqslant T\leqslant 100)$ 。接下来行每行输入六个整数,$N,A,B,X,Y,Z$ (均小于 $10^9$ ) 输出时每行一个数,表示最小花费

加入题单

上一题 下一题 算法标签: