[AGC044A] Pay to Win

题目描述

你有一个数字$0$ ，你希望得到数字$N$。

你可以通过以下操作更改数字，需要支付一定数量的硬币：

• 将当前数乘$2$，需要$A$硬币。
• 将当前数乘$3$，需要$B$硬币。
• 将当前数乘$5$，需要$C$硬币。
• 将当前数加$1$或减$1$，需要$D$硬币。

你可以按任意顺序和任意次数执行这些操作。

最少需要多少硬币才能得到$N$？

你需要解决$T$组测试用例。

输入格式

第一行包含一个整数。

$T$

随后的$T$行代表$T$个测试用例。每行包含五个整数。

$N$ $A$ $B$ $C$ $D$

输出格式

对于每个测试用例，输出一行表示答案。

样例 #1

样例输入 #1

5
11 1 2 4 8
11 1 2 2 8
32 10 8 5 4
29384293847243 454353412 332423423 934923490 1
900000000000000000 332423423 454353412 934923490 987654321

样例输出 #1

20
19
26
3821859835
23441258666

提示

约束

• $1\ \le\ T\ \le\ 10$
• $1\ \le\ N\ \le\ 10^{18}$
• $1\ \le\ A,\ B,\ C,\ D\ \le\ 10^9$
• $N,\ A,\ B,\ C,\ D$ 都是整数。

Sample Explanation 1

对于第一个测试用例，达到最低成本$20$的一系列操作是：

• 初始 $x = 0$.
• 用$8$个硬币使其加$1(x = 1)$
• 用$1$个硬币使其乘$2(x = 2)$
• 用$1$个硬币使其乘$2(x = 4)$
• 用$2$个硬币使其乘$3(x = 12)$
• 用$8$个硬币使其减$1(x = 11)$

对于第二个测试用例，达到最低成本$19$的一系列操作是：

• 初始 $x = 0$.
• 用$8$个硬币使其加$1(x = 1)$
• 用$1$个硬币使其乘$2(x = 2)$
• 用$2$个硬币使其乘$5(x = 10)$
• 用$8$个硬币使其减$1(x = 11)$