凑出 N

时间限制：2s
空间限制：1024MB

题目描述

初始有整数 $P=0$。你可以任意次、以任意顺序执行以下三种操作：

• 将 $P$ 增加 1，代价为 $X$；
• 将 $P$ 增加 $A$，代价为 $Y$；
• 将 $P$ 增加 $B$，代价为 $Z$。

求使 $P=N$ 的最小总代价。你需要回答 $T$ 组测试数据。

输入格式

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

样例输出 1

11
10
1
139
436604

数据范围

• $1\le T\le100$；
• $1\le N,A,B,X,Y,Z\le10^9$。

下表中对 $N,A,B$ 的限制均对该输入中的每组测试数据成立。