Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_10_07 - Eksperyment

rdza1 września to dla wielu powrót do szkoły oraz powrót do nauki przedmiotów zarówno tych lubianych, jak i nie. Bajteusz nigdy nie lubił chemii. Dzisiajsza lekcja jednak bardzo go zaciekawiła. Nauczyciel kazał uczniom przeprowadzić eksperyment pokazujący działanie różnych rodzajów kwasów. Polegał on na upuszczaniu w ściśle określonych momentach kropli stężonego kwasu na długi metalowy pręt. Celem ćwiczenia było zmierzenie czasu jaki jest potrzebny aby cały pręt pokrył się rdzą. Bajteusz szybko zauważył, że ognisko rdzy na pręcie zainicjowane przez spadającą kroplę rozszerza się w tempie 1mm/sek w obydwu kierunkach aż do końca pręta. Postanowił, że tym razem zabłyśnie na nielubianym przez siebie przedmiocie i napisze program który szybko za niego wszystko policzy. Przy okazji potrenuje do zbliżającej się wielkimi krokami Olimpiady Informatycznej.

 

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite, kolejno: 1<=d<=109 oraz 1<=n<=105 które oznaczają kolejno długość pręta w milimetrach oraz liczbę kropel kwasu upuszczonych na niego. Każdy z kolejnych n wierszy zawiera dwie liczby całkowite, kolejno: 0<=x<=d oraz 0<=t<=109. Liczba x oznacza odległość spuszczonej kropli w milimetrach od lewego końca metalu, a liczba t - moment upuszczenia kropli na pręt, mierzony w sekundach od początku eksperymentu.

Wyjście

W jedynym wierszu wyjścia należy wypisać najmniejszą całkowitą liczbę sekund od początku eksperymentu do momentu, w którym cały metal będzie pokryty rdzą.

Przykład

Wejście:
10 4
2 0
8 1
5 1
7 4

Wyjście: 3

Wyjaśnienie do przykładu:

Po pierwszej sekundzie eksperymentu rdzą będzie pokryty fragment od 1 do 3 milimetra metalu, po drugiej fragment od początku do 6 milimetra i od 7 do 9 milimetra.


Dodane przez:Adam Bąk
Data dodania:2013-09-11
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:AlgoLiga 10
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.