Cankurtaranlar (Platin)#10426
Çiftçi John ineklerinin rahatlamasına ve daha fazla süt vermesine yardımcı olacağını düşünerek inekleri için bir yüzme havuzu açtı.
Güvenliği sağlamak için, her biri gün içinde sürekli bir zaman aralığını kapsayan bir vardiyada çalışan ineği cankurtaran olarak işe alır. Basitlik için, havuzun her gün zaman anından 10^9 zaman anına kadar açık olduğunu varsayalım, böylece her vardiya ineğin vardiyasının başlangıç ve bitiş anlarını gösteren iki tam sayı ile tanımlanabilir. Örneğin, vardiyasına t = 4 anında başlayıp t = 7 anında bitiren bir cankurtaran, üç zaman birimini kapsar (vardiyanın uç noktaları zaman anlarını belirtir).
Ne yazık ki, Çiftçi John ödeyebileceğinden cankurtaran daha fazla işe aldı. Tam olarak cankurtaranı işten çıkarması gerektiğine göre, kalan cankurtaranların vardiyalarının kapsayabileceği maksimum zaman miktarı nedir? Bir zaman anı, en az bir cankurtaranın görevde olması durumunda kapsanmış sayılır.
İlk satır iki tam sayı ve k~(1 \le k \le 100, k \le n \le 10^5) içerir. Sonraki satırın her biri iki tam sayı s_i ve t_i~(0 \le s_i < t_i \le 10^9) — . cankurtaranın vardiyasının başlangıç ve bitiş anları içerir. Tüm vardiya uç noktaları birbirinden farklıdır. Farklı cankurtaranların vardiyaları çakışabilir.
Çiftçi John cankurtaranı işten çıkardıktan sonra hâlâ kapsanabilecek maksimum zaman miktarını yazdırın.
Örnek 1
Çiftçi John, vardiyaları ve olan cankurtaranları işten çıkarmalıdır.