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