Vecmāmiņai Aldai mīļākais seriāls ir “Mīlestības bedre”. Šim seriālam ir S sērijas. Katrai sērijai ir savs garums sekundēs. Aldas mazdēls Andris ir dabūjis visas “Mīlestības bedres” sērijas un grib iepriecināt vecmāmiņu, tai uzdāvinot visu sēriju ierakstus DVD diskos, lai vecmāmiņa varētu labi pavadīt laiku no rīta līdz vakaram un lai nejaušas iesnaušanās (kas Aldai gadās) neradītu satraukumu par neredzētām sērijām. Andrim ir pietiekams daudzums vienādu DVD matricu, lai ierakstītu visas sērijas. Katrā matricā var ierakstīt X sekundes.

Andris grib ievērot šādus principus:

1. Katrai sērijai ir jāaizņem minimālais disku skaits (piemēram, ja sērijas ierakstam vajag 10 diskus, bet tās fragmentus gribas ierakstīt 12 dažādos diskos, tad to nedrīkst darīt);
2. Sērijas jāieraksta diskos hronoloģiskā secībā, t.i., to secību nedrīkst mainīt.

Uzrakstiet programmu, kas aprēķina mazāko iespējamo disku skaitu, kādā var ierakstīt visas seriāla sērijas, ievērojot Andra principus!

Ievaddatu pirmajā rindā doti divi naturāli skaitļi S (S ≤ 10⁶ ) un X (X ≤ 10⁶), kas atdalīti ar tukšumzīmi. Katrā no nākamajām S faila rindām dots naturāls skaitlis, kas nepārsniedz 10⁶, - vienas seriāla sērijas garums sekundēs. Ievaddatu (i+1)-ajā rindā ir dots i-tās sērijas garums.

Izvaddatu vienīgajā rindā jāizvada viens naturāls skaitlis - mazākais disku skaits, kādā var ierakstīt visas seriāla sērijas.

Pirmajā testpiemērā vienīgais variants ir – pirmajā diskā ierakstīt pirmo sēriju, otrajā – otro, bet trešajā – trešo un ceturto sēriju.

Otrajā testpiemērā var pirmajā diskā ierakstīt pirmās sērijas pirmās piecas sekundes. Otrajā diskā – pirmās sērijas atlikušās divas sekundes, kā arī pirmās divas sekundes no otrās sērijas. Trešajā diskā – otrās sērijas atlikušās piecas sekundes. 

Uzdevums izmantots 22. Latvijas informātikas olimpiādē 2009. gadā.