Teleportlar
Siz qərbdən şərqə doğru düz xətt boyunca Misiri keçmək üçün yarışlarda iştirak edirsiniz. Əvvəlcə xəttin qərb ucunda yerləşirsiniz. Yarış qaydalarına görə yalnız xətt boyunca və yalnız şərqə doğru hərəkət etməlisiniz.
Xətt üzərində N teleport mövcuddur. Hər teleport xətt üzərində iki nöqtə ilə təyin olunur. Bu nöqtələrdən birinə çatdığınızda, teleport sizi dərhal digər nöqtəyə aparır (bu, cari mövqeyinizdən həm şərqə, həm də qərbə ola bilər). Teleportasiya edildikdən sonra xətt boyunca şərqə doğru hərəkət etməyə davam etməlisiniz. Yolunuzda olan teleport nöqtələrindən qaça bilməzsiniz. Eyni mövqedə yerləşən iki teleport nöqtəsi yoxdur. Bütün teleport nöqtələri xəttin başlanğıcı və sonu arasında yerləşir.
Hər teleportasiya edildikdə bir xal qazanırsınız. Yarışın məqsədi mümkün qədər çox xal toplamaqdır. Qazandığınız xalları maksimuma çatdırmaq üçün səyahətinizə başlamazdan əvvəl xəttə ən çox M yeni teleport əlavə etməyə icazə verilir. Yeni teleportlardan istifadə edərkən də xal qazanırsınız.
Yeni teleport nöqtələrini istədiyiniz yerdə yerləşdirə bilərsiniz (hətta tam olmayan mövqelərdə), lakin onlar artıq digər teleport nöqtələri tərəfindən tutulan mövqeləri tutmamalıdır, yəni bütün teleportlara aid olan bütün nöqtələrin mövqeləri fərqli olmalıdır. Yeni teleport nöqtələri də xəttin başlanğıcı və sonu arasında yerləşməlidir.
Qeyd etmək lazımdır ki, teleportların əlavə edilmə üsulundan asılı olmayaraq, xəttin sonuna çatmaq həmişə mümkündür.
Tapşırıq
Verilmiş N teleport nöqtələrinin mövqeləri və əlavə edə biləcəyiniz M yeni teleportların sayı əsasında əldə edilə biləcək maksimum xal sayını hesablayan proqram yazın.
Məhdudiyyətlər
1 <= N <= 1 000 000 (N – xətt üzərində əvvəlcədən olan teleportların sayı)
1 <= M <= 1 000 000 (M – əlavə edə biləcəyiniz maksimum yeni teleportların sayı)
1 <= WX < EX <= 2 000 000 (WX və EX – teleportun qərb və şərq nöqtələrinə qədər olan məsafələr)
Giriş verilənləri
Proqramınız aşağıdakı formatda standart girişdən məlumat oxumalıdır:
• 1-ci sətir N tam ədədini ehtiva edir – xətt üzərində əvvəlcədən olan teleportların sayı.
• 2-ci sətir M tam ədədini ehtiva edir – əlavə edə biləcəyiniz maksimum yeni teleportların sayı.
• Növbəti N sətirdən hər biri bir teleportu təsvir edir, burada i-ci sətir i-ci teleportu təsvir edir. Hər sətir boşluqla ayrılmış iki tam ədəd W_i və E_i ehtiva edir. Bu ədədlər teleportun qərb və şərq nöqtələrinə qədər olan məsafələri təmsil edir.
Verilmiş teleport nöqtələrindən heç biri eyni mövqedə yerləşmir. Hərəkət etməli olduğunuz xətt 0 mövqeyində başlayır və 2 000 001 mövqeyində bitir.
Çıxış verilənləri
Proqramınız standart çıxışa yalnız bir sətir yazmalıdır ki, bu da əldə edilə biləcək maksimum xal sayını ehtiva edir.