Seqmentlər
Verilmiş N parça var. Hər birinin uzunluğu santimetrlə ölçülən tam ədəddir. Bu parçaları düz xətt üzərində elə yerləşdirmək lazımdır ki, aşağıdakı şərtlər təmin edilsin:
Parçaların sol ucları arasındakı məsafələr də santimetrlə ifadə olunan tam ədədlər olmalıdır.
Düz xətt üzərində uzunluğu L olan bir parça seçmək mümkün deyil ki, bu parçanın içərisinə ən azı iki verilmiş parça tamamilə daxil olsun (parça [a, b] parçası [c, d] parçasının içərisinə tamamilə daxil olur, əgər c ≤ a və b ≤ d).
Parçaların bütün ucları arasında ən sol və ən sağ uclar arasındakı məsafə, əvvəlki iki şərti təmin edən bütün yerləşdirmələr üçün mümkün olan ən kiçik məsafədir.
Ən sol və ən sağ uclar arasında santimetrlə ən kiçik məsafənin nə ola biləcəyini tapın.
Giriş verilənləri
Birinci sətir tam ədədləri N və M (1 ≤ N ≤ 50000) ehtiva edir. Növbəti N sətirin hər biri bir parçanın uzunluğunu ehtiva edir (1 ≤ L ≤ 1000000000). Hər bir parçanın uzunluğu [1, 10^9] aralığında yerləşir.
Çıxış verilənləri
Tək tam ədəd - parçaların ucları arasındakı mümkün olan ən kiçik məsafə.