Ok I will prove it, so my memory doesn’t betray me.
Consider some set of n-1 type of objects. Each pair must consume at least one from this set. So we can show upper bound of sum-mx.
This upper bound can only be reached if we take one from mx, and one from the rest.
Therefore we can show if (mx >= sum-mx) answer is sum-mx.
Let’s consider it to be lesser. We are now considering the case where
mx < sum - mx.
Let’s take a pair from the largest two elements. Do a little bit of casework when 2*mx is just less than sum, there can only be 2 of mx, therefore we can reach a state where only one object is left.
So answer is
if(mx >= sum - mx) sum - mx else sum/2
@dishantpawar95 I explicitly mentioned k = 2 twice.