Avets P62616

En lloc d’estar entrenant, els representants de la UPC al SWERC es dediquen a fer turisme no convencional per París, mirant com la gent embolica avets a un mercat de nadal. Com que l’algorisme d’embolicar avets és molt costós, una de les persones que s’hi dedica, la Marie, que és asmàtica, cada cert temps ha de “xutar-se” ventolin.

Aquest és el problema a resoldre: La Marie inicialment té energia $k$. Encara li queden $n$ avets per embolicar, en un ordre fixat, i cada avet $i$ li consumeix energia $e_i$. Cada cop que es “xuta” ventolin, l’energia li torna al nivell original $k$, i cada cop que embolica un avet, l’energia li disminueix en $e_i$. La Marie no pot tenir mai energia negativa, i només pot “xutar-se” ventolin entre avets. Quin és el mínim nombre de cops que ha de “xutar-se”?

Entrada

L’entrada consisteix en diversos casos, cadascun amb $n$ i $k$, seguits dels $e_i$. Podeu suposar $1 \le n \le 10^5$, $1 \le k \le 10^6$, i $1 \le e_i \le k$.

Sortida

Per a cada cas, escriviu el mínim nombre de “xutes”.