{"problem":{"name":"Minimal payments","description":{"content":"There are $N$ kinds of coins used in the Kingdom of Atcoder: $A_1$\\-yen, $A_2$\\-yen, $\\ldots$, $A_N$\\-yen coins.   Here, $1=A_1 < \\ldots < A_N$ holds, and $A_{i+1}$ is a multiple of $A_i$ for every $1","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc231_e"},"statements":[{"statement_type":"Markdown","content":"There are $N$ kinds of coins used in the Kingdom of Atcoder: $A_1$\\-yen, $A_2$\\-yen, $\\ldots$, $A_N$\\-yen coins.  \nHere, $1=A_1 < \\ldots < A_N$ holds, and $A_{i+1}$ is a multiple of $A_i$ for every $1\\leq i \\leq N-1$.\nWhen paying for a product worth $X$ yen using just these coins, what is the minimum total number of coins used in payment and returned as change?\nAccurately, when $Y$ is an integer at least $X$, find the minimum sum of the number of coins needed to represent exactly $Y$ yen and the number of coins needed to represent exactly $Y-X$ yen.\n\n## Constraints\n\n*   All values in input are integers.\n*   $1 \\leq N \\leq 60$\n*   $1=A_1 < \\ldots <A_N \\leq 10^{18}$\n*   $A_{i+1}$ is a multiple of $A_i$ for every $1\\leq i \\leq N-1$.\n*   $1\\leq X \\leq 10^{18}$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $X$\n$A_1$ $\\ldots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc231_e","tags":[],"sample_group":[["3 87\n1 10 100","5\n\nIf we pay with one $100$\\-yen coin and receive one $10$\\-yen coin and three $1$\\-yen coins as the change, the total number of coins will be $5$."],["2 49\n1 7","7\n\nIt is optimal to pay with seven $7$\\-yen coins."],["10 123456789012345678\n1 100 10000 1000000 100000000 10000000000 1000000000000 100000000000000 10000000000000000 1000000000000000000","233"]],"created_at":"2026-03-03 11:01:14"}}