A[] - values.
B[] - rewards.

1. sort A[] by not increasing order.
2. i=1..n    B[j] += A[i],  which B[j] - minimal value of B[].
3. while ( not <= K)
     try to equate with minimal of B[] and all other B[]s.
     try to equate with maximal of B[] and all other B[]s.
4. print.

only how to equate ? use simple DP!

if M=2 we get knapsack problem, and how to solve it faster than N*sum(A[i])?
or your solution uses fact that a B[]s are approximately equal?