Here is my solution which is different from the official one. (My English is very poor, sorry)

Let dp[i][j] be the maximum number of digits of the answer, which is made with i matches and has j as the first(highest) digit.

Thus we can easily get dp[i + c[A[k]]][A[k]] = max(dp[i + c[A[k]]][A[k]], dp[i][A[j]] + 1), where A[i] means the i-th available digit and c[i] means the cost of digit i.

Finally, we can greedily output the answer. For i, the number of matches left now, consider a best j with max{f[i][j]}. If there exists some js with the same value, just use the maximum j. This strategy is correct, because when we compare two numbers, we first consider their total length, and then from high digits to low digits.

Here is my solution for a better understanding :)

The main insight for these type of questions where you must output a big integer that is maximum is to first maximize length. If there are multiple answers of the same length, break ties by choosing the lexicographically larger number.

I maintained two arrays. F(i) represents the maximum length possible with exact cost i A(i, d) represents the length of the number with total cost i and last digit d.

Here is my code and explanation.