AT_arc210_c [ARC210C] Fair Coin Partition

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.

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 the maximum possible total value of coins distributed to each person.

### Sample Explanation 1 - 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 $ . ### 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.