Xilasedicilər (Platin)
Fermer Con inəkləri üçün hovuz açdı, düşünərək ki, bu, onların rahatlamasına və daha çox süd istehsal etməsinə kömək edəcək.
Təhlükəsizliyi təmin etmək üçün o, hər biri gün ərzində müəyyən fasiləsiz bir müddəti əhatə edən növbəsi olan n inəyi xilasedici kimi işə götürür. Sadəlik üçün hovuz hər gün 0 vaxtından 10^9 vaxtına qədər açıqdır, buna görə də hər növbəni iki tam ədədlə təsvir etmək olar - inəyin növbəyə başladığı və bitirdiyi vaxt. Məsələn, t = 4 vaxtında başlayan və t = 7 vaxtında bitən xilasedici üç vaxt vahidini əhatə edir (nəzərə alın ki, son nöqtələr "vaxt nöqtələri"dir).
Təəssüf ki, fermer Con k xilasedicini saxlamaq üçün kifayət qədər vəsaiti olmadığı üçün işə götürdü. O, dəqiq k xilasedicini işdən çıxarmalı olduğunu nəzərə alaraq, qalan xilasedicilərin növbələri ilə hələ də əhatə oluna biləcək maksimum vaxt nə qədərdir? Bir vaxt intervalı əhatə olunur, əgər orada ən azı bir xilasedici varsa.
Giriş Məlumatları
Birinci sətir n və k (k ≤ n ≤ 100000, 1 ≤ k ≤ 100) ehtiva edir. Növbəti n sətirin hər biri xilasedicini 0..10^9 aralığında iki tam ədəd şəklində təsvir edir - xilasedicinin növbəyə başladığı və bitirdiyi vaxt. Bütün nöqtələr fərqlidir. Müxtəlif xilasedicilərin növbələri üst-üstə düşə bilər.
Çıxış Məlumatları
Fermer Con k xilasedicini işdən çıxarsa, əhatə oluna biləcək maksimum vaxtı göstərin.
Nümunə
Con 1..8 və 7..15 əhatə edən xilasediciləri işdən çıxarmalıdır.