#### Proof

Suppose we have an optimal solution:

`S_maximum = min(a_smallest, a_j) + S_other`

where `a_smallest`

is the smallest number in the integer set and `a_j`

is greater or equal to `a_smallest`

.

Let us proof the following statement.

If there is a number (or numbers) `a_between_a_smallest_and_a_j`

between `a_smallest`

and `a_j`

then it must satisfy to the condition: the second number paired with `a_between_a_smallest_and_a_j`

**can be only with the same value** as `a_between_a_smallest_and_a_j`

, i.e. there are two variants for optimal solution:

`S_maximum = min(a_smallest, a_j) + S_other`

, where`a_j`

- next smallest after`a_smallest`

`S_maximum = min(a_smallest, a_j) + min(a2, a2) + min(a3, a3) + ... + S_other`

, where`a_smallest <= a2 <= a3 <= a_j`

.

We prove by contradiction.

Suppose there is a number `a_i`

between: `a_smallest < a_i < a_j`

in solution. His paired number is `a_k`

. So the optimal sum looks like: `S_maximum = min(a_smallest, a_j) + min(a_i, a_k) + S_other.`

If `a_i < a_k`

, then we can get greater sum with `S_maximum = min(a_smallest, a_i) + min(a_k, a_j) + S_other`

, because `a_j > a_i`

and `a_k > a_i`

. Contradiction!

If `a_i > a_k`

, then we can greater sum with `S_maximum = min(a_smallest, a_k) + min(a_i, a_j) + S_other`

. Contradiction!

So for fixed smallest number `a1`

the optimal solution looks like: `min(a1, a2) + other`

where `a2`

- next smallest after `a1`

or `min(a1, aj) + min(a2, a2) + min(a3, a3) + other`

where `a1 <= a2 <= a3 <= aj`

. Both this variants we can rewrote without decreasing sum into `min(a1, a2) + min(a2, a3) + min(a3, a3) + min(a3, aj) + min(a4, a5)`

where `a1<=a2=a2(second)=a3=a3=a3=a3<=aj`

- *but this is just sorted numbers paired*! So `a_smallest`

can be *only* paired with next smallest number. Iterating through `S_other`

with this logic we just get solution with sorting idea.

#### Main idea

The logic behind this is if we have an optimal solution `S_max = min(a_smallest, a_k) + S_optimal_other`

we can replace `a_k`

with the next smallest number after `a_smallest`

(`a_smallest_2`

) and put `a_k`

in old `a_smallest_2`

position without decreasing sum. Repeating this trick for `S_optimal_other`

we get sorted pairs.