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