Recently a friend of mine gave me a problem to solve. You are given n numbers and initialize sum=0. You are doing steps until there is only one number left. In every step you take two numbers a and b, remove them from the set, add (a+b) to sum (sum+=a+b) and insert number (a+b) to our set. What is the smallest sum that you can achieve after this process?

Example: you are given numbers (1,2,3) and sum=0
1. You may take (1,2) then sum=3 or (2,3) then sum=5 or (1,3) then sum=4
2. Now you have numbers (3,3) or (5,1) or (4,2) and after this step sums are respectively sum=9 or sum=11 or sum=10
3. So the lowest sum you can achieve is 9

So I came up with a solution. In each step you take two smallest numbers. But I cannot prove that this strategy is correct. Are you able to prove or discard it?