Xilasedicilər (Platin)#10426
Fermer Con inəkləri üçün hovuz açıb, bunun onların rahatlaşmasına və daha çox süd verməsinə kömək edəcəyini düşünür.
Təhlükəsizliyi təmin etmək üçün o, inəyi xilasedici kimi işə götürür, hər biri gün ərzində davamlı bir vaxt aralığını əhatə edən növbədə işləyir. Sadəlik üçün qəbul edək ki, hovuz hər gün anından 10^9 anına qədər açıqdır, buna görə də hər növbə iki tam ədədlə — inəyin növbəsinin başlama və bitmə anları ilə təsvir oluna bilər. Məsələn, növbəsinə t = 4 anında başlayıb t = 7 anında bitirən xilasedici üç vahid vaxtı əhatə edir (növbənin uc nöqtələri vaxt anlarını bildirir).
Təəssüf ki, fermer Con ödəyə biləcəyindən xilasedici artıq işə götürüb. Onun dəqiq xilasedicini işdən çıxarmalı olduğunu nəzərə alaraq, qalan xilasedicilərin növbələrinin hələ də əhatə edə biləcəyi maksimum vaxt müddəti nə qədərdir? Əgər ən azı bir xilasedici növbədədirsə, həmin vaxt anı əhatə olunmuş sayılır.
Birinci sətirdə iki tam ədəd — və k~(1 \le k \le 100, k \le n \le 10^5) verilir. Sonrakı sətirdən hər biri iki tam ədəd — s_i və t_i~(0 \le s_i < t_i \le 10^9) — -ci xilasedicinin növbəsinin başlama və bitmə anlarını ehtiva edir. Bütün növbələrin uc nöqtələri fərqlidir. Müxtəlif xilasedicilərin növbələri üst-üstə düşə bilər.
Fermer Con xilasedicini işdən çıxardıqdan sonra hələ də əhatə oluna biləcək maksimum vaxt müddətini çap edin.
Nümunə 1
Fermer Con növbələri və olan xilasedicilərı işdən çıxarmalıdır.