Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Денино брдо, иначе највеће брдо на свету, препуно је вештица. За одржавање јавног реда и мира на Денином брду задужена је главна и најшколованија вештица Анђелија. Она је управо одбранила докторску дисертацију под називом “Лаки летећи објекти” на ФЦМ-у (Факултет за црну магију у Црној Реци).
Тајна сваке успешне вештице је у непрестаној вежби и понављању различитих магичних трикова. Анђелија је одлучила да данас вежба са лебдећим кутијама у својој кући. Она је поставила одређени број кутија уз зид и сваку подигла на неку висину. Зид је висок \(N\) метара и широк \(M\) метара (формалније, може се представити као матрица димензије \(N \times M\)), док је свака кутија висока \(1\) метар и широка \(1\) метар (формалније, може се представити као једно поље у матрици која означава зид). На свакој висини се налази одређени број кутија које лебде и тај број је строго већи од \(0\) за сваку висину. Кутије на некој висини су поређане једна до друге, тако да се могу означити једним интервалом. \([L_i, R_i]\). За сваку висину \(i\) су нам дата два броја \(L_i\), \(R_i\), који означавају да је прва кутија на тој висини на координати \((i, L_i)\), а последња на координати \((i, R_i)\).
Нормално, Денино брдо насељавају и скроз обични људи, који и не слуте да су око њих вештице. Зато Анђелија жели да остане неупадљива, а кутије које лебде то сигурно нису. Одлучила је да поређа кутије тако да изгледа да оне стоје једна на другој (граде неку фигуру која по мало личи на пирамиду). За овај подухват је потребно да интервал кутија на одређеној висини буде подинтервал кутија на нижој висни (формалније, да важе следећи услови: \(L_{i-1} \leq L_i\) и \(R_i \leq R_{i-1}\) за \(2 \leq i \leq N\)).
У једном потезу Анђелија може да помери све кутије на одређеној висини за \(1\) метар лево или десно. Кутије не могу отићи ван граница зида, односно да поседују координату по ширини мању од \(1\) и већу \(M\). Такође, није дозвољено мењати висине кутија. Да ли можете помоћи Анђелији да одреди минималан број потеза да своје кутије доведе у ред.
Прва линија стандардног улаза садржи два броја, \(N\) и \(M\), висину и ширину зида редом.
Свака од наредних \(N\) линија садржи по два цела броја, \(L_i\) и \(R_i\), почетак и крај интервала кутија које лебде на висини од \(i\) метара.
У јединој линији стандардног излаза исписати минималан број потеза који Анђелија треба да направи.
4 8
1 4
4 7
4 5
3 343 3
1 1
2 2
3 32Решење првог примера је представљено на слици испод.
У другом примеру је оптимално померити кутију на висини \(1\) за један метар у десно, док кутију на висини \(3\) за један метар у лево.
Тест примери су подељени у 5 подзадатка: