lampas3 Lampas - 3 1 sek.  Uzdevums Lejasbebru ciema vienīgā iela ir pilnīgi taisna un šķērso visu ciemu. Tā ir tieši M metrus gara, un dažādās vietās virs tās ir piekārtas lampas. Sākotnēji visas lampas ir ieslēgtas. Katra lampa, ja vien tā ir ieslēgta, apgaismo ielas daļu abos ielas virzienos tik tālu, cik augstu tā ir piekārta. Ciema padome, vēloties minimizēt izmaksas, ir nolēmusi dažas lampas izslēgt, taču tā, lai nerastos neveikla situācija, ka kāds ielas posms, kas agrāk tika apgaismots, vairs netiek apgaismots (ielas posms ir apgaismots, ja katru tā punktu apgaismo vismaz viena lampa). Uzrakstiet programmu, kas aprēķina, kādu lielāko skaitu lampu var vienlaicīgi izslēgt, ievērojot iepriekš aprakstīto noteikumu!    Ievaddati Teksta faila lampas3.dat pirmajā rindā doti divi naturāli skaitļi, kas atdalīti ar tukšumzīmi, - lampu skaits N (1 ≤ N ≤ 100 000) un ielas garums metros M (1 ≤ M ≤ 109). Katrā no nākamajām N faila rindām dots vienas lampas apraksts - divi veseli skaitļi xi un hi, kas atdalīti ar tukšumzīmi. xi ir attālums metros no ielas sākuma (0 ≤ xi ≤ M). hi ir augstums metros, kādā lampa ir piekārta (1 ≤ hi ≤ 109). Zināms, ka visas lampas ir piekārtas atšķirīgās vietās.    Izvaddati Teksta faila lampas3.rez vienīgajā rindā jāizvada vesels nenegatīvs skaitlis - lielākais lampu skaits, ko var vienlaicīgi izslēgt tā, ka apgaismoto ielas posmu kopgarums paliktu nemainīgs.    Piemērs lampas3.dat lampas3.rez 7 11 1 1 2 2 3 2 10 1 11 2 8 1 2 4 4 Viens variants – izslēgt lampas, kas failā minētas kā 1.,2.,3. un 4. Šis variants parādīts zīmējumā. Otrs variants – izslēgt lampas, kas failā minētas kā 1.,2.,3. un 5.     lampas3.dat lampas3.rez 5 4 0 2 1 2 2 2 3 2 4 2 4 Pietiek atstāt ieslēgtu lampu, kas failā minēta kā trešā.    Atsauces Uzdevums izmantots 21. Latvijas informātikas olimpiādē 2008. gadā. Drukāšanai