Трамплинlər
Bessi ikiölçülü şəbəkədə yerləşir və yalnız koordinat oxlarına paralel istiqamətdə hərəkət edə bilir. O, hərəkətə (0, 0) nöqtəsindən başlayır və məqsədi (n, n) nöqtəsinə çatmaqdır. Şəbəkədə p sayda tramplin mövcuddur. Hər bir tramplin müəyyən bir nöqtədə (x[1], y[1]) yerləşir və Bessi bu tramplindən istifadə etdikdə, o, (x[2], y[2]) nöqtəsinə keçəcək.
Bessi yalnız yuxarı və ya sağa hərəkət edə bilər və heç vaxt sola və ya aşağıya hərəkət etmir. Tramplinlər də eyni qaydada konfiqurasiya olunub, yəni onlar da heç vaxt sola və ya aşağıya göndərmirlər. Bessi'nin keçməli olduğu minimal məsafəni hesablayın.
Giriş məlumatları
Birinci sətir iki tam ədəd n (1 ≤ n ≤ 10^9) və p (1 ≤ p ≤ 10^5) ehtiva edir. Növbəti p sətirin hər biri dörd tam ədəd x[1], y[1], x[2], y[2] ehtiva edir, burada x[1] ≤ x[2] və y[1] ≤ y[2].
Bütün tramplin başlanğıc nöqtələri və eniş yerləri fərqlidir.
Çıxış məlumatları
Bir tam ədəd çıxarın - Bessi'nin (n, n) nöqtəsinə çatmaq üçün keçməli olduğu minimal məsafə.
Nümunə
Optimal marşrut belədir:
Piyada (0, 0) nöqtəsindən (0, 1) nöqtəsinə (1).
Tramplinlə (0, 2) nöqtəsinə.
Piyada (0, 2) nöqtəsindən (1, 2) nöqtəsinə (1).
Tramplinlə (2, 3) nöqtəsinə.
Piyada (2, 3) nöqtəsindən (3, 3) nöqtəsinə (1).
Piyada keçilən yolun ümumi uzunluğu = 3.