Java

using arrays

The Task Professor Smith needs new research equipment to further his research to save the manatees in the Indian Lagoon River. The money made from the trading shares of Volatity Inc. will be used to purchase lab equipment. Currently the store is having a sale in which one can buy three items, but pay for only two items. The professor cannot pass up such a good deal. However, the store that sells the lab equipment makes you pay for the most expensive items. For an example, when Professor Smith checks out with seven items, costing 400, 350, 300, 250, 200, 150, and 100 dollars, the total will be 1500 dollars. In this case the savings is 450 dollars. You realize that in the case there is a stragety that saves more money by going to the check-out counter multiple times. For example, if the professor first takes items that cost 400, 300 and 250, the savings will 250 dollars. If the professor then brings the item that costs 150 there is not discout. But if the professor then brings the last items that costs 350, 200 and 100, there is an additional savings of 100 dollars. This all adds up to a total savings of 450 dollars.

Your job is to find the maximum discount Professor Smith can get

Input

The first line of input gives the number of items Professor Smith is buying, 1n200000. The next line gives the prices of these items, which are integers 1pi200000.

Sample Input and Output

Input

6

400 100 200 350 300 250

Output

400