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.