Trambolinlər#9604
Bessi iki ölçülü şəbəkədədir, burada o, yalnız koordinat oxlarına paralel istiqamətlərdə hərəkət edə bilər. O, nöqtəsindən hərəkətə başlayır və nöqtəsinə çatmaq istəyir. Ona kömək etmək üçün şəbəkədə trambolin yerləşdirilmişdir. Hər bir trambolin sabit bir (x_1, y_1) nöqtəsindən başlayır və əgər Bessi ondan istifadə etsə, onu (x_2, y_2) nöqtəsinə köçürür.
Bessi irəliləyişə yönəlmiş inəkdir, ona görə də özünə yalnız yuxarı və ya sağa hərəkət etməyə icazə verir, heç vaxt sola və ya aşağıya hərəkət etmir. Eynilə, hər bir trambolin də onu heç vaxt sola və ya aşağıya köçürməyəcək şəkildə qurulmuşdur. Başqa sözlə, hər bir trambolin üçün x_1 \le x_2 və y_1 \le y_2 şərtləri ödənilir.
Bessinin nöqtəsinə çatmaq üçün piyada getməli olduğu minimum məsafə nə qədərdir?
Birinci sətirdə iki tam ədəd n~(1 \le n \le 10^9) və p~(1 \le p \le 10^5) verilmişdir.
Sonrakı sətirin hər birində Bessini (x_1, y_1) nöqtəsindən (x_2, y_2) nöqtəsinə köçürən trambolini təsvir edən dörd tam ədəd x_1, y_1, x_2, y_2 verilmişdir, burada x_1 \le x_2 və y_1 \le y_2 şərtləri ödənilir.
Bütün tramplinlərin başlanğıc və son nöqtələri, eləcə də hədəf nöqtə fərqlidir.
Bessinin nöqtəsinə çatmaq üçün piyada getməli olduğu minimum məsafəni bildirən bir tam ədəd çap edin.
Bessinin optimal marşrutu aşağıdakı kimidir:
Bessi nöqtəsindən nöqtəsinə gedir, məsafə qət edir.
Bessi trambolindən istifadə edərək nöqtəsindən nöqtəsinə keçir.
Bessi nöqtəsindən nöqtəsinə gedir, məsafə qət edir.
Bessi trambolindən istifadə edərək nöqtəsindən nöqtəsinə keçir.
Bessi nöqtəsindən nöqtəsinə gedir, məsafə qət edir.
Piyada gedilən yolun ümumi uzunluğu vahiddir.
Nümunə 1