Fair Coin Partition

AtCoder

IDarc210_c

Time2000ms

Memory256MB

Difficulty—

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$ people. However, the total value of coins distributed to each person must be equal. It is allowed to have coins that are not distributed. Find the maximum possible total value of coins distributed to each person. You are given $T$ test cases; solve each of them. ## Constraints * $1\leq T\leq 10^5$ * $1\leq N\leq 2\times 10^5$ * $1\leq M\leq 10^9$ * $0\leq A_i\leq 10^9$ * The sum of $N$ over all test cases is at most $2\times 10^5$. * All input values are integers. ## Input The input is given from Standard Input in the following format: $T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$ Each test case is given in the following format: $N$ $M$ $A_0$ $A_1$ $\ldots$ $A_{N-1}$ [samples]

Samples

Input #1

5
3 1
123 456 789
3 1000
123 456 789
2 3
6 14
2 3
11 14
30 4
15 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

Output #1

83583
0
42
50
19401302040124704218001124023

*   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$.
*   For the second test case, there is no choice but to distribute $0$ coins to everyone.
*   For the third test case, the total value of coins distributed to each person can be made $42$ as follows:
    *   To the $1$\-st person, distribute $2$ coins of value $10^0$ and $4$ coins of value $10^1$.
    *   To the $2$\-nd person, distribute $2$ coins of value $10^0$ and $4$ coins of value $10^1$.
    *   To the $3$\-rd person, distribute $2$ coins of value $10^0$ and $4$ coins of value $10^1$.
*   For the fourth test case, the total value of coins distributed to each person can be made $50$ as follows:
    *   To the $1$\-st person, distribute $0$ coins of value $10^0$ and $5$ coins of value $10^1$.
    *   To the $2$\-nd person, distribute $0$ coins of value $10^0$ and $5$ coins of value $10^1$.
    *   To the $3$\-rd person, distribute $10$ coins of value $10^0$ and $4$ coins of value $10^1$.

API Response (JSON)

{
  "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$ peopl...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments