Chef And His Society

Chef is an algorithmist so his friend has given him a problem. Problem is that you have been given an array A(indexed 1 through N). There is a thresold value $Th$. You need to find a maximum integer value M so that $S$ is greater or equal to $Th$. Where, $S$ = $\sum_{i=1}^{N} max(A_i-M,0)$ For example - If $A$ is $1,2,3,4,5,6,7$ and $ Th= 9$, then $M$ will be 3 and $S = max(1-3,0) + max(2-3,0