/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 700 点
問題文
N 種類のコインがあります．0\leq i\leq N-1 について (1+i) 種類目のコインは価値が 10^{i} で，あなたはこのコインを A_i 枚所持しています．
これらのコインを，M 人に配ることにしました．ただし，1 人あたりに配るコインの価値の総和が等しくなるようにします．また，配らないコインがあってもよいです．
1 人あたりに配るコインの価値の総和としてありうる最大値を求めてください．
T 個のテストケースが与えられるので，それぞれについて答えを求めてください．
制約
- 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 以下．
- 入力される値はすべて整数．
入力
入力は以下の形式で標準入力から与えられます．
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられます．
N M
A_0 A_1 \ldots A_{N-1}
出力
1 人あたりに配るコインの価値の総和としてありうる最大値を出力してください．
入力例 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
出力例 1
83583 0 42 50 19401302040124704218001124023
- 1 番目のテストケースについて，すべてのコインを 1 人に配ると，1 人あたりに配るコインの価値の総和は 123\times 10^0+456\times 10^1+789\times 10^2=83583 になります．
- 2 番目のテストケースについて，全員に 0 枚のコインを配るしかありません．
- 3 番目のテストケースについて，次のようにすることで 1 人あたりに配るコインの価値を 42 にすることができます．
- 1 番目の人に，価値 10^0 のコインを 2 枚，価値 10^1 のコインを 4 枚配る．
- 2 番目の人に，価値 10^0 のコインを 2 枚，価値 10^1 のコインを 4 枚配る．
- 3 番目の人に，価値 10^0 のコインを 2 枚，価値 10^1 のコインを 4 枚配る．
- 4 番目のテストケースについて，次のようにすることで 1 人あたりに配るコインの価値を 50 にすることができます．
- 1 番目の人に，価値 10^0 のコインを 0 枚，価値 10^1 のコインを 5 枚配る．
- 2 番目の人に，価値 10^0 のコインを 0 枚，価値 10^1 のコインを 5 枚配る．
- 3 番目の人に，価値 10^0 のコインを 10 枚，価値 10^1 のコインを 4 枚配る．
Score : 700 points
Problem Statement
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}
Output
Output the maximum possible total value of coins distributed to each person.
Sample 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
Sample 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.