Factory bought a whole houses as a workshop, we prepare the whole building is divided into a number of workshops, splitting the house price is equal to decorate a company rules be broken up in the area of the building, if want to split for area covers an area of 200 room for 80, and 50 three workshops, for the first time will be split to area of the building two rooms in 120 and 80, 200, the second area covers an area of 120 room split into two rooms for the 70 and 50, 120, the total cost is 320, if use another plan, the first will be an area of 200 homes split for 150 and 50, 200, the second room to spin off the area of 150 to 80 and 70 rooms, 150, the total cost of 350, obviously the first kind of plan cost less, please write a program designed for the director of the least expensive spin-off plan,

Input format:
Input for the two lines, the first conduct an integer n, the number of workshop said, the second act n positive integers, with a space interval, given every workshop area, n is not more than 100000, and ensure that the final result is less than 2
? 31
?? ,

The output format:
Output is an integer, said it would spin off the premises is minimum cost of a new n workshop,

Input the sample:
8
1 1 1 1 2 3 4 5
The output sample:
49

CodePudding user response:

18=9, 9; 9=4, 5; 9=4, 5; 5=2, 3; 4=2, 2; 2=1, 1; 2=1, 1; 18,9,9,5,4,2,2=49