Segments#5533
Given segments, each with an integer length measured in centimeters, you must arrange these segments on a line so that the following conditions are satisfied:
The distances between the left ends of the segments are also integers.
It is not possible to find a segment of length on the line that completely contains at least two of the given segments. That is, a segment is said to be fully contained in another segment if c \leq a and b \leq d.
Among all possible arrangements of the segments that meet the above conditions, the distance between the leftmost and rightmost ends of the segments should be minimized.
Determine the smallest possible distance, in centimeters, between the leftmost and rightmost ends of the segments.
The first line contains two integers and (1 \leq N \leq 50000). Each of the following lines contains the length of a segment (1 \leq L \leq 10^9).
Print a single integer — the minimal possible distance between the ends of the segments.
Example 1