Intrappolata nel fieno (Gold)#11175
L'agricoltore John ha ricevuto una partita di grandi balle di fieno e le ha posizionate in vari punti lungo una strada che conduce al suo granaio. Sfortunatamente, si è completamente dimenticato che la mucca Bessie pascola lungo questa strada, e ora rischia di rimanere intrappolata tra le balle di fieno!
Ogni balla ha una dimensione s_j e una posizione p_j, che ne definisce la collocazione su una strada monodimensionale. Bessie può muoversi liberamente lungo la strada, incluso raggiungere una posizione occupata da una balla, ma non può attraversare una balla.
C'è un'unica eccezione: se Bessie percorre in una direzione unità di distanza, acquisisce una velocità sufficiente per sfondare e distruggere definitivamente qualsiasi balla di fieno la cui dimensione sia strettamente inferiore a . Naturalmente, dopo la distruzione di una balla, potrebbe aprirsi ulteriore spazio davanti a lei, permettendole di accelerare di nuovo e distruggere altre balle.
Bessie può liberarsi se alla fine riesce a sfondare o la balla di fieno più a sinistra o quella più a destra. Determinare la lunghezza totale della strada costituita da tutte le posizioni iniziali reali dalle quali Bessie non riesce a liberarsi.
Nella prima riga è contenuto un numero intero n~(1 \le n \le 10^5). In ciascuna delle successive righe viene descritta una balla di fieno: due numeri interi ne indicano la dimensione e la posizione, ciascuno nell'intervallo 1 \ldots 10^9. Tutte le posizioni sono distinte.
Stampare un singolo numero intero — la lunghezza totale della strada dalla quale Bessie non riesce a liberarsi.
Esempio 1