{"problem":{"name":"Fair Coin Partition","description":{"content":"There are $N$ types of coins. For $0\\leq i\\leq N-1$, the $(1+i)$\\-th type of coin has a value of $10^{i}$, and you possess $A_i$ of these coins. You have decided to distribute these coins to $M$ peopl","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc210_c"},"statements":[{"statement_type":"Markdown","content":"There are $N$ types of coins. For $0\\leq i\\leq N-1$, the $(1+i)$\\-th type of coin has a value of $10^{i}$, and you possess $A_i$ of these coins.\nYou have decided to distribute these coins to $M$ people. However, the total value of coins distributed to each person must be equal. It is allowed to have coins that are not distributed.\nFind the maximum possible total value of coins distributed to each person.\nYou are given $T$ test cases; solve each of them.\n\n## Constraints\n\n*   $1\\leq T\\leq 10^5$\n*   $1\\leq N\\leq 2\\times 10^5$\n*   $1\\leq M\\leq 10^9$\n*   $0\\leq A_i\\leq 10^9$\n*   The sum of $N$ over all test cases is at most $2\\times 10^5$.\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach test case is given in the following format:\n\n$N$ $M$\n$A_0$ $A_1$ $\\ldots$ $A_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc210_c","tags":[],"sample_group":[["5\n3 1\n123 456 789\n3 1000\n123 456 789\n2 3\n6 14\n2 3\n11 14\n30 4\n15 9 2 66 23 2 4 1 1 32 4 80 9 10 47 14 8 7 3 16 2 39 77 4 4 2 38 64 1 2","83583\n0\n42\n50\n19401302040124704218001124023\n\n*   For the first test case, if all coins are distributed to one person, the total value of coins distributed to each person is $123\\times 10^0+456\\times 10^1+789\\times 10^2=83583$.\n*   For the second test case, there is no choice but to distribute $0$ coins to everyone.\n*   For the third test case, the total value of coins distributed to each person can be made $42$ as follows:\n    *   To the $1$\\-st person, distribute $2$ coins of value $10^0$ and $4$ coins of value $10^1$.\n    *   To the $2$\\-nd person, distribute $2$ coins of value $10^0$ and $4$ coins of value $10^1$.\n    *   To the $3$\\-rd person, distribute $2$ coins of value $10^0$ and $4$ coins of value $10^1$.\n*   For the fourth test case, the total value of coins distributed to each person can be made $50$ as follows:\n    *   To the $1$\\-st person, distribute $0$ coins of value $10^0$ and $5$ coins of value $10^1$.\n    *   To the $2$\\-nd person, distribute $0$ coins of value $10^0$ and $5$ coins of value $10^1$.\n    *   To the $3$\\-rd person, distribute $10$ coins of value $10^0$ and $4$ coins of value $10^1$."]],"created_at":"2026-03-03 11:01:14"}}