I'm having a hard time with finding an efficient algorithm for this problem:

I have a very large 2D array filled with integers ranging from 0 to some specified maximum N.
I know need to increase the sum of all the elements by an integer amount m (possibly very large).
This m should be distrubuted around the array randomly, however maintaining that each element does not exceed N.

If there are k elements in the array, and m>k*N, then of course the array should be filled with N's.

Can you think of a smart and fast way to do this?