Pay to Win

AtCoder

IDagc044_a

Time2000ms

Memory256MB

Difficulty—

You start with the number $0$ and you want to reach the number $N$. You can change the number, paying a certain amount of coins, with the following operations: * Multiply the number by $2$, paying $A$ coins. * Multiply the number by $3$, paying $B$ coins. * Multiply the number by $5$, paying $C$ coins. * Increase or decrease the number by $1$, paying $D$ coins. You can perform these operations in arbitrary order and an arbitrary number of times. What is the minimum number of coins you need to reach $N$? **You have to solve $T$ testcases.** ## Constraints * $1 \le T \le 10$ * $1 \le N \le 10^{18}$ * $1 \le A, B, C, D \le 10^9$ * All numbers $N, A, B, C, D$ are integers. ## Input The input is given from Standard Input. The first line of the input is $T$ Then, $T$ lines follow describing the $T$ testcases. Each of the $T$ lines has the format $N$ $A$ $B$ $C$ $D$ [samples]

Samples

Input #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

Output #1

20
19
26
3821859835
23441258666

For the first testcase, a sequence of moves that achieves the minimum cost of $20$ is:

*   Initially $x = 0$.
*   Pay $8$ to increase by $1$ ($x = 1$).
*   Pay $1$ to multiply by $2$ ($x = 2$).
*   Pay $1$ to multiply by $2$ ($x = 4$).
*   Pay $2$ to multiply by $3$ ($x = 12$).
*   Pay $8$ to decrease by $1$ ($x = 11$).

For the second testcase, a sequence of moves that achieves the minimum cost of $19$ is:

*   Initially $x = 0$.
*   Pay $8$ to increase by $1$ ($x = 1$).
*   Pay $1$ to multiply by $2$ ($x = 2$).
*   Pay $2$ to multiply by $5$ ($x = 10$).
*   Pay $8$ to increase by $1$ ($x = 11$).

API Response (JSON)

{
  "problem": {
    "name": "Pay to Win",
    "description": {
      "content": "You start with the number $0$ and you want to reach the number $N$. You can change the number, paying a certain amount of coins, with the following operations: *   Multiply the number by $2$, paying ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc044_a"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You start with the number $0$ and you want to reach the number $N$.\nYou can change the number, paying a certain amount of coins, with the following operations:\n\n*   Multiply the number by $2$, paying ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments