Problem
Ghiaccio vuole camminare per le calli di Venezia. Tuttavia, oggi è piuttosto irritabile, il che rende difficile camminare.
Venezia è una città piuttosto popolare tra i turisti, che però chiamano la città "Venezia" in maniera straniera, invece del corretto "Venezia".
Questo fa arrabbiare molto Ghiaccio, ma non vuole rimanere furioso dopo la passeggiata. Pertanto, ha deciso che a volte si tappava le orecchie quando passava davanti ai turisti per non arrabbiarsi di nuovo.
Ghiaccio ha una barra della calma interna che si riempie di un punto al secondo (quando Ghiaccio esce di casa, il valore di questa barra è zero).
Se però Ghiaccio passa da un gruppo turistico, in cui ci sono d persone, allora la sua calma diminuisce di d, perché si arrabbia per l'errata pronuncia del nome della città. Ma se Ghiaccio passa tappandosi le orecchie, la sua calma non diminuirà.
Se a un certo punto la scala della calma diventa negativa, allora Ghiaccio impazzirà, il che è estremamente inaccettabile.
Ghiaccio conosce molto bene Venezia, quindi sa che durante la passeggiata passerà circa n gruppi turistici, per ognuno dei quali si sa che sarà nel secondo con il numero t
i e in questo gruppo ci saranno d< sub>i persone.
Sulla base di queste informazioni, calcola il numero minimo di volte che Ghiaccio dovrà tapparsi le orecchie per non impazzire mentre cammina.
Inserimento:
La prima riga contiene un singolo numero intero n (1 ≤ n ≤ 200000) — il numero di gruppi turistici attorno ai quali passerà Ghiaccio.
Quindi seguono n righe, ciascuna contenente due numeri interi separati da spazio: t
i e d
i (1 ≤ t
i ,&thinsp ;d
i ≤ 10
9) — il numero del secondo in cui Ghiaccio passerà accanto all'i-esimo gruppo turistico, e il numero delle persone che lo compongono. Tutti i t
i sono distinti e sono in ordine crescente.
Uscita:
Stampa un singolo numero intero — il numero minimo di volte che Ghiaccio dovrà tapparsi le orecchie per non impazzire.
Esempi:
| Input |
Uscita |
3
3 2
5 4
6 3
| 1 |
5
1 2
3 2
5 3
6 2
7 3
| 2 |
Spiegazioni:
Nel primo esempio, Ghiaccio deve tapparsi le orecchie mentre passa vicino al secondo gruppo.
Poi, alla fine del terzo secondo, la sua calma sarà pari a 1 (3 ha recuperato per ogni secondo di cammino, ma diminuito di 2 passando dal primo gruppo).
Entro la fine del quinto secondo la calma sarà pari a 3 (la calma non diminuirà dal secondo gruppo, perché Ghiaccio si è tappato le orecchie al passaggio).
E alla fine del sesto secondo, la calma sarà pari a 3+1-3 = 1.
Inoltre, la sua calma non diminuisce mai.