Sosial məsafə

Fermer Con, inəklərinin sağlamlığına COWVID-19 adlı çox yoluxucu mal-qara xəstəliyinin yayılmasından sonra narahatdır.

Xəstəliyin yayılmasını məhdudlaşdırmaq üçün, Conun n inəyi "sosial məsafə" tətbiq etməyə və fermada yayılmağa qərar verib. Ferma, otlaq üçün ot olan m qarşılıqlı kəsişməyən intervallardan ibarət bir ədədi xətt formasındadır. İnəklər müxtəlif tam nöqtələrdə yerləşmək istəyirlər, hər biri otla örtülmüşdür, belə ki, d dəyərini maksimuma çatdırsınlar, burada d inəklərin ən yaxın cütü arasındakı məsafəni təmsil edir. İnəklərə d-nin mümkün olan ən böyük dəyərini müəyyən etməyə kömək edin.

Giriş Məlumatları

Birinci sətir n (2 ≤ n ≤ 10^5) və m (1 ≤ m ≤ 10^5) ədədlərini ehtiva edir. Növbəti m sətirin hər biri iki tam ədəd a və b şəklində intervalı təsvir edir, burada 0 ≤ a ≤ b ≤ 10^18. Heç bir iki interval bir-birini örtmür və ya son nöqtələrində toxunmur. İntervalın son nöqtəsində dayanan inək otun üstündə dayanmış hesab olunur.

Çıxış Məlumatları

Bütün inək cütlərinin bir-birindən d vahid məsafədə yerləşməsi üçün mümkün olan ən böyük d dəyərini çıxarın. d > 0 olan bir həllin mövcudluğu təmin edilir.

Nümunə

d = 2 əldə etməyin bir yolu inəkləri 0, 2, 4, 6 və 9 mövqelərində saxlamaqdır.