The wood company Moon-Wood is dealing with the business of cutting down the old trees in the Alpine forest and selling them. The company used to carry the trunks to the factory via rivers and cut them into smaller pieces in the factory. However, the company has some difficulty in carrying the big trunks to the factory due to the decrease in the water level. In order to solve this problem the company decided to cut trunks into pieces, in the forest, and float the pieces to the factory.

Cutting a trunk into two pieces has a cost, which is equal to the length of the trunk. Make a program to calculate the minimum cost of cutting a trunk with the length L into the N smaller pieces with the lengths of L1, L2… Ln. At a time, you can cut a trunk only into two pieces.

Input specification
The input consists of two lines. In the first line, there are two integers: L and N, where L denotes the length of the trunk and N denotes the number of the pieces and 1 ≤ L ≤ 100.000; 1 ≤ N ≤ 40.000. In the second line, there are N positive integers separated with a space representing the lengths of the pieces. The sum of the numbers in the second line is always equal to L.

Output specification
Output contains an integer that is the minimum cost of cutting the given trunk into the given smaller pieces.