AT_arc210_c [ARC210C] Fair Coin Partition

$ N $ 種類のコインがあります． $ 0\leq i\leq N-1 $ について $ (1+i) $ 種類目のコインは価値が $ 10^{i} $ で，あなたはこのコインを $ A_i $ 枚所持しています． これらのコインを， $ M $ 人に配ることにしました．ただし， $ 1 $ 人あたりに配るコインの価値の総和が等しくなるようにします．また，配らないコインがあってもよいです． $ 1 $ 人あたりに配るコインの価値の総和としてありうる最大値を求めてください． $ T $ 個のテストケースが与えられるので，それぞれについて答えを求めてください．

入力は以下の形式で標準入力から与えられます． > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられます． > $ N $ $ M $ $ A_0 $ $ A_1 $ $ \ldots $ $ A_{N-1} $

$ 1 $ 人あたりに配るコインの価値の総和としてありうる最大値を出力してください．

### Sample Explanation 1 - $ 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 $ 枚配る． ### 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 $ - すべてのテストケースにわたる $ N $ の総和は $ 2\times 10^5 $ 以下． - 入力される値はすべて整数．