Intrappolata nel fieno (Argento)#11171
Il fattore John ha ricevuto un carico di grandi balle di fieno e le ha disposte in varie posizioni lungo la strada che collega il suo granaio alla sua casa. Ogni balla ha una dimensione s_j e si trova in una posizione separata p_j su questa strada. In questo momento la mucca Bessie si trova nella posizione , dove non c'è nessuna balla di fieno.
Bessie può muoversi liberamente lungo la strada, compreso l'avvicinarsi fino alla posizione occupata da una balla, ma non può attraversare una balla. Tuttavia, c'è un'eccezione: se corre in una direzione per una distanza di unità, acquisisce una velocità sufficiente per sfondare e distruggere definitivamente qualsiasi balla la cui dimensione sia strettamente inferiore a . Dopo che Bessie sfonda una balla, potrebbe avere abbastanza spazio libero per prendere di nuovo velocità e sfondare altre balle.
Il fattore John sta ora ridipingendo la sua casa e il suo granaio e vuole assicurarsi che Bessie non possa raggiungere nessuno dei due (le mucche e la vernice fresca non sono proprio la combinazione migliore!). Per questo motivo FJ vuole garantire che Bessie non riesca mai a sfondare la balla di fieno più a sinistra o più a destra, rimanendo di fatto intrappolata tra le due balle estreme.
FJ può aggiungere fieno a una balla a sua scelta per aiutare a tenere Bessie intrappolata. Aiutalo a determinare la quantità minima di fieno aggiuntivo che è necessario aggiungere a una delle balle affinché Bessie non possa fuggire.
Nella prima riga si trovano due numeri interi e b~(1 \le n \le 10^5), dove è il numero di balle di fieno e è la posizione iniziale di Bessie.
Ognuna delle successive righe contiene due numeri interi s_j e p_j, che indicano rispettivamente la dimensione e la posizione della -esima balla di fieno.
Tutte le dimensioni e le posizioni sono comprese tra e 10^9, inclusi.
Stampa un singolo numero intero: la quantità minima di fieno aggiuntivo che FJ deve aggiungere a una delle balle affinché Bessie non possa fuggire.
Stampa se non è possibile impedire la fuga di Bessie.
Esempio 1