There are only M-N+1 possible averages and their corresponding minimums (I think it is not monotonic -- so cannot binary search)... so possibly solve the problem in one set given an average...? The latter I still do not have a polynomial time solution... would need to think a bit more.