Stivali da neve#10409
In fattoria è inverno, e quindi — neve! Il sentiero dalla casa del contadino al fienile è composto da piastrelle, numerate per comodità da a , e la piastrella è coperta da uno strato di neve di profondità f_i piedi.
Il contadino John inizia il suo cammino dalla piastrella e deve arrivare alla piastrella per svegliare le mucche. La piastrella si trova sotto il tetto della casa del contadino, e la piastrella — sotto il tetto del fienile, perciò su queste piastrelle non c'è neve. Ma per poter mettere piede su qualsiasi altra piastrella, il contadino John deve indossare gli stivali!
Nello zaino per il brutto tempo del contadino John ci sono paia di stivali, numerati da a . Alcune paia sono più resistenti di altre, mentre altre permettono di muoversi più agilmente. Precisamente, il paio permette al contadino John di mettere piede nella neve di profondità non superiore a s_i piedi e di avanzare non più di d_i piastrelle per passo.
Sfortunatamente, gli stivali sono disposti in modo tale che in ogni momento al contadino John è accessibile solo il paio più in alto. Perciò in ogni momento il contadino John può o indossare il paio più in alto di stivali (gettando via il paio che indossa in quel momento), oppure gettare via il paio più in alto di stivali (rendendo accessibile il paio successivo).
Il contadino John può cambiare gli stivali solo stando su una piastrella. Se su questa piastrella giace uno strato di neve di profondità piedi, allora sia gli stivali che toglie, SIA gli stivali che indossa devono resistere a una neve di profondità non inferiore a piedi. Le paia intermedie di stivali che getta via senza indossarle non devono soddisfare questa limitazione.
Aiutate il contadino John a minimizzare le perdite: determinate il numero minimo di paia di stivali che dovrà gettare via per arrivare al fienile. Inizialmente il contadino John è scalzo.
Nella prima riga sono dati due numeri interi e b~(2 \le n, b \le 250). Nella seconda riga sono dati numeri interi f_1, f_2, \ldots, f_n~(0 \le f_i \le 10^9), dove f_i — è la profondità della neve sulla piastrella . Si garantisce che f_1 = f_n = 0.
Ciascuna delle successive righe contiene due numeri interi. La (i + 2)-esima riga contiene i numeri s_i e d_i~(0 \le s_i \le 10^9, 1 \le d_i \le n - 1) — rispettivamente la profondità massima della neve in cui si può mettere piede con il paio , e la lunghezza massima del passo con il paio .
Gli stivali sono elencati dall'alto verso il basso: il paio è il più in alto nello zaino del contadino John, il paio è quello successivo, e così via.
Stampate un singolo numero intero — il numero minimo di paia di stivali che il contadino John dovrà gettare via. Si garantisce che il contadino John possa arrivare al fienile.
Esempio 1