Сегменты
Дано N отрезков. Длина каждого из них, измеренная в сантиметрах – некое целое число. Требуется расположить эти отрезки на прямой таким образом, чтобы были выполнены следующие условия:
Расстояния между левыми концами отрезков в сантиметрах также выражаются целыми числами.
На прямой невозможно взять отрезок длиной L, в который полностью попадают хотя бы два данных отрезка (отрезок [a, b] полностью попадает в отрезок [c, d], если c ≤ a и b ≤ d).
Среди всех концов отрезков, расстояние между самым левым и самым правым - наименьшее возможное для всех расположений отрезков, удовлетворяющих предыдущим двум пунктам.
Найдите, какое наименьшее расстояние, опять таки в сантиметрах, может быть между самым левым и самым правым концами отрезков.
Входные данные
Первая строка содержит целые числа N и M (1 ≤ N ≤ 50000). Каждая из следующих N строк содержит длину отрезка (1 ≤ L ≤ 1000000000. Длина каждого из отрезков находится в диапазоне [1, 10^9]).
Выходные данные
Единственное целое число – минимальное возможное расстояние между концами отрезков.