Nosaukums
Šoseja "A1" (a1)
Laika limits
1.00s
Atmiņas limits
256.0 MB

Definīcija

Valsts galvenā šoseja ir "A1" un tās uzturēšanai kārtībā tiek pievērsta pastiprināta uzmanība. Katru pavasari tiek noskaidroti ziemā radušies bojājumi un to novēršanai tiek izsūtītas bojājumu novēršanas brigādes.

Ir zināms, ka pirmajos M šosejas metros bojājumu nav. Visa šoseja tiek sadalīta M metrus garos posmos tā, ka pirmais posms sākas K-tajā metrā (1 ≤K≤M) un šie posmi seko viens otram bez atstarpēm. Tāpēc, piemēram, L-tais posms sākas šosejas (K+(L-1)*M)-tajā metrā.

Katra bojājumu novēršanas brigāde var apkalpot tieši vienu šādu posmu, neatkarīgi no tā, cik bojājumu tajā ir. Protams, ja kādā posmā bojājumu nav, tad brigāde turp nav jāsūta.

Uzrakstiet programmu, kas nosaka, kāds mazākais bojājumu novēršanas brigāžu skaits ir nepieciešamas un kuros šosejas metros šajā gadījumā vajag sākt šosejas dalījumu posmos!


Ievaddatu raksturojums

Ievaddatu pirmajā rindā dotas divu naturālu skaitļu M (posma garums) un N (bojājumu skaits), kas atdalīti ar tukšumsimbolu. Zināms, ka 1≤M,N≤100000.

Faila otrajā rindā doti N naturāli skaitļi, kas atdalīti ar tukšumsimboliem - bojāto šosejas metru numuri augošā secībā (pirmais šosejas metrs tiek apzīmēts ar 1, otrais ar 2, utt.). Katrs no skaitļiem ir lielāks par M un nepārsniedz 2*109.


Izvaddatu raksturojums

Izvaddatu pirmajā rindā jāizvada mazākais nepieciešamais bojājumu novēršanas brigāžu skaits. Faila otrajā rindā jāizvada visu to šosejas metru numuri augošā secībā, kur var sākties šosejas dalījums posmos, lai nepieciešamais brigāžu skaits būtu vismazākais.


Piezīmes

Uzdevums izmantots Horvātijas informātikas olimpiādē 2003.gadā


Paraugdati

Stdin
3 5
4 5 7 8 9
Stdout
2
1

Stdin
4 3
7 14 15
Stdout
2
1 2 4

Stdin
2 10
3 4 7 8 12 13 14 15 20 21
Stdout
7
1 2

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.