题目描述

我们有一个整数$P=0$。通过以任意顺序、任意次数执行以下三种操作，找到使$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

在第一个测试用例中，以下是一种使$P=10$的方法，成本为$11$，这是最优的。

• 将$P$增加$3$，使$P=3$，成本为$3$。
• 将$P$增加$1$，使$P=4$，成本为$2$。
• 将$P$增加$3$，使$P=7$，成本为$3$。
• 将$P$增加$3$，使$P=10$，成本为$3$。