AT_arc210_c [ARC210C] Fair Coin Partition

共有 $N$ 种硬币。对于 $0 \leq i \leq N-1$，第 $i+1$ 种硬币的面值为 $10^i$，你拥有 $A_i$ 枚这种硬币。 你打算将这些硬币分给 $M$ 个人。要求每个人分到的硬币总价值相等。可以有硬币不被分配。 请你求出每个人可以分到的最大总价值。 给定 $T$ 组测试数据，请分别求解。

输入通过标准输入给出，格式如下： > $T$ > $\mathrm{case}_1$ > $\mathrm{case}_2$ > $\vdots$ > $\mathrm{case}_T$ 每组测试数据格式如下： > $N \; M$ > $A_0 \; A_1 \; \ldots \; A_{N-1}$

对于每组测试数据，输出每个人可以分到的最大总价值。

### 样例解释 1 - 对于第一组数据，如果将所有硬币都分给一个人，则每个人可以分到的总价值为 $123 \times 10^0 + 456 \times 10^1 + 789 \times 10^2 = 83583$。 - 对于第二组数据，只能让每个人都分到 $0$ 元的硬币。 - 对于第三组数据，每个人可以分到 $42$ 元，具体分配如下： - 第 $1$ 个人分到 $2$ 个面值为 $10^0$ 的硬币，以及 $4$ 个面值为 $10^1$ 的硬币。 - 第 $2$ 个人分到 $2$ 个面值为 $10^0$ 的硬币，以及 $4$ 个面值为 $10^1$ 的硬币。 - 第 $3$ 个人分到 $2$ 个面值为 $10^0$ 的硬币，以及 $4$ 个面值为 $10^1$ 的硬币。 - 对于第四组数据，每个人可以分到 $50$ 元，具体分配如下： - 第 $1$ 个人分到 $0$ 个面值为 $10^0$ 的硬币，以及 $5$ 个面值为 $10^1$ 的硬币。 - 第 $2$ 个人分到 $0$ 个面值为 $10^0$ 的硬币，以及 $5$ 个面值为 $10^1$ 的硬币。 - 第 $3$ 个人分到 $10$ 个面值为 $10^0$ 的硬币，以及 $4$ 个面值为 $10^1$ 的硬币。 ### 数据范围 - $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$ - 所有测试数据中 $N$ 的总和不超过 $2 \times 10^5$ - 所有输入均为整数。 由 ChatGPT 5 翻译