分数: 400 点
问题陈述
你从数字开始 0 并且您想要达到的号码 N.
您可以通过支付一定的金币来更改号码,操作如下:
- 将数字乘以 2, 支付 A 硬币。
- 将数字乘以 3, 支付 B 硬币。
- 将数字乘以 5, 支付 C 硬币。
- 增加或减少数量 1, 支付 D 硬币。
您可以按任意顺序和任意次数执行这些操作。
您需要达到的最少金币数量是多少 N?
你必须解决 T 测试用例。
约束
- 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 是整数。
输入
输入由标准输入给出。输入的第一行是
T
然后, T 行如下描述 T 测试用例。 每个 T 行的格式为
N A B C D
输出
对于每个测试用例,在标准输出上打印答案,后跟换行符。
示例输入 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
对于第一个测试用例,实现最小成本的一系列移动 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).