Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
A Denino Brdo hegy, mint tudjuk a világon a legmagasabb hegy, tele van boszorkányokkal. A hegyen a rendfenntartásért a legokosabb boszorkány, Anđelija felel. Ő nemrég védte meg “Könnyű lebegő objektumok” témájú doktori disszertációját az FME-n ( a Fekete Folyó nevű városban székelő Fekete Mágia Egyetemen).
A sikeres boszorkányok titka az állandó gyakorlás, és a különböző trükkök folyamatos ismételgetése. Anđelija eldöntötte, hogy ma otthon fog gyakorolni lebegő dobozokkal. Elhelyezett megfelelő számú dobozt a fal mellett, majd felemelte őket bizonyos magasságra. A fal \(N\) méter magas és \(M\) méter széles (elképzelhetjük, mint egy \(N \times M\) dimenziójú mátrixot), míg minden doboz \(1\) méter magas és \(1\) méter széles (a dobozt elképzelhetjük, mint a falat helyettesítő mátrix egy mezőjét). Minden magasságszinten \(0\)-tól különböző számú doboz lebeg. A dobozok minden szinten sorban helyezkednek el, így ábrázolhatjuk őket egy \([L_i, R_i]\) intervallummal. Minden \(i\) magasságszintre adott két szám: \(L_i\), \(R_i\), amelyek azt mutatják, hogy azon a magasságon az első doboz koordinátája \((i, L_i)\), az utolsó dobozé pedig \((i, R_i)\).
A Denino Brdo hegyen természetesen közönséges emberek is laknak, akik nem tudják, hogy körülöttük boszorkányok is élnek. Anđelija nem szeretne feltűnő lenni, azonban a lebegő dobozok elárulhatnák. Elhatározta, hogy a dobozokat úgy rendezi át, mintha azok egymáson helyezkednének el (piramishoz hasonló alakzatot kialakítva). Ennek az elrendezésnek az a feltétele, hogy a dobozokat definiáló intervallumok egy adott magasságon az alsóbb szint intervallumának részintervalluma legyen ( vagyis érvényes kell hogy legyen a következő feltétel: \(L_{i-1} \leq L_i\) és \(R_i \leq R_{i-1}\), ahol \(2 \leq i \leq N\)).
Egy mozdulattal Anđelija egy adott magasságon az összes dobozt elmozdíthatja \(1\) méterrel jobbra vagy balra. A dobozok nem hagyhatják el a fal felületét, vagyis vízszintesen nem lehet a koordinátájuk \(1\)-nél kisebb és \(M\)-nél nagyobb. A dobozok magasságát nem lehet megváltoztatni. Segítsetek Anđelijanak, hogy megtalálja az minimális számú elmozdítást ahhoz , hogy a dobozok elrendezése a megfelelő legyen.
A szabványos bemenet első sorában az \(N\) és \(M\) számok állnak, melyek a sorban fal magasságát és szélességét jelentik.
Minden következő (összesen \(N\)) sor mindegyike két egész számot, \(L_i\) és \(R_i\) számokat tartalmaz, amelyek az \(i\) méter magasan lebegő dobozok intervallumának helyét (kezdetét és végét) definiálják.
A szabványos kimenet egyetlen sorában kiíratni az elmozdítások minimális számát, amelyet Anđelijanak el kell végezni.
4 8
1 4
4 7
4 5
3 343 3
1 1
2 2
3 32Az első példa magyarázata a lenti képen látható.
A második példa esetében az optimális megoldás az, ha a dobozokat \(1\) magasan 1 méterrel jobbra, míg a \(3\) magasan lebegő dobozokat 1 méterrel balra mozgatja.
A tesztpéldák feloszthatók 5 alfeladatra: