Дано \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 Единственное целое число -- минимальное возможное расстояние между концами отрезков.