Segments
Given N segments, each with an integer length measured in centimeters, you need to arrange these segments on a line such 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 L on the line that completely contains at least two of the given segments. A segment [a, b] is considered fully contained within another segment [c, d] if c ≤ a and b ≤ d.
Among all possible placements 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.
Input
The first line contains two integers, N and M (1 ≤ N ≤ 50000). Each of the following N lines contains the length of a segment (1 ≤ L ≤ 1000000000). The length of each segment is within the range [1, 10^9].
Output
Output a single integer — the minimum possible distance between the ends of the segments.