{"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 $A$ coins.\n*   Multiply the number by $3$, paying $B$ coins.\n*   Multiply the number by $5$, paying $C$ coins.\n*   Increase or decrease the number by $1$, paying $D$ coins.\n\nYou can perform these operations in arbitrary order and an arbitrary number of times.\nWhat is the minimum number of coins you need to reach $N$?\n**You have to solve $T$ testcases.**\n\n## Constraints\n\n*   $1 \\le T \\le 10$\n*   $1 \\le N \\le 10^{18}$\n*   $1 \\le A, B, C, D \\le 10^9$\n*   All numbers $N, A, B, C, D$ are integers.\n\n## Input\n\nThe input is given from Standard Input. The first line of the input is\n\n$T$\n\nThen, $T$ lines follow describing the $T$ testcases. Each of the $T$ lines has the format\n\n$N$ $A$ $B$ $C$ $D$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc044_a","tags":[],"sample_group":[["5\n11 1 2 4 8\n11 1 2 2 8\n32 10 8 5 4\n29384293847243 454353412 332423423 934923490 1\n900000000000000000 332423423 454353412 934923490 987654321","20\n19\n26\n3821859835\n23441258666\n\nFor the first testcase, a sequence of moves that achieves the minimum cost of $20$ is:\n\n*   Initially $x = 0$.\n*   Pay $8$ to increase by $1$ ($x = 1$).\n*   Pay $1$ to multiply by $2$ ($x = 2$).\n*   Pay $1$ to multiply by $2$ ($x = 4$).\n*   Pay $2$ to multiply by $3$ ($x = 12$).\n*   Pay $8$ to decrease by $1$ ($x = 11$).\n\nFor the second testcase, a sequence of moves that achieves the minimum cost of $19$ is:\n\n*   Initially $x = 0$.\n*   Pay $8$ to increase by $1$ ($x = 1$).\n*   Pay $1$ to multiply by $2$ ($x = 2$).\n*   Pay $2$ to multiply by $5$ ($x = 10$).\n*   Pay $8$ to increase by $1$ ($x = 11$)."]],"created_at":"2026-03-03 11:01:13"}}