← 返回题目列表

AtCoder · agc044_a

A. 付费获胜

中文机器翻译题面 查看原题

分数: 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).