Problem
Ghiaccio quer andar pelas ruas de Veneza. Porém, hoje ele está bastante irritável, o que dificulta a deambulação.
Veneza é uma cidade bastante popular entre os turistas, que, no entanto, chamam a cidade de "Veneza" de forma estrangeira, em vez do correto "Venezia".
Isso deixa Ghiaccio muito bravo, mas ele não quer ficar furioso depois da caminhada. Por isso, decidiu que às vezes tapava os ouvidos ao passar por turistas para não se irritar novamente.
O Ghiaccio possui uma barra de calma interna que reabastece em um ponto por segundo (quando o Ghiaccio sai de casa, o valor dessa barra é zero).
Porém, se Ghiaccio passa por um grupo de turistas, no qual há d pessoas, então sua calma diminui em d, porque ele fica bravo com a pronúncia errada do nome da cidade. Mas se Ghiaccio passar tapando os ouvidos, sua calma não diminuirá.
Se em algum momento a escala calma se tornar negativa, então Ghiaccio ficará furioso, o que é extremamente inaceitável.
Ghiaccio conhece muito bem Veneza, por isso sabe que durante a caminhada passará por n grupos de turistas, para cada um dos quais se sabe que estará no segundo com o número t
i e neste grupo haverá d< sub>i pessoas.
Com base nessas informações, calcule o número mínimo de vezes que Ghiaccio terá que tapar os ouvidos para não enlouquecer ao caminhar.
Entrada:
A primeira linha contém um único inteiro n (1 ≤ n ≤ 200000) — o número de grupos turísticos pelos quais Ghiaccio passará.
Em seguida, seguem n linhas, cada uma contendo dois inteiros separados por espaço: t
i e d
i (1 ≤ t
i ,&thinsp ;d
i ≤ 10
9) — o número do segundo em que Ghiaccio passará pelo i-ésimo grupo turístico e o número de pessoas nele. Todos os t
i são distintos e estão em ordem crescente.
Saída:
Imprima um único inteiro — o número mínimo de vezes que Ghiaccio terá que tapar os ouvidos para não enlouquecer.
Exemplos:
| Entrada |
Saída |
3
3 2
5 4
6 3
| 1 |
5
1 2
3 2
5 3
6 2
7 3
| 2 |
Explicações:
No primeiro exemplo, Ghiaccio tem que tapar os ouvidos ao passar perto do segundo grupo.
Então, ao final do terceiro segundo, sua calma será igual a 1 (3 ele compensou para cada segundo da caminhada, mas diminuiu 2 passando pelo primeiro grupo).
Ao final do quinto segundo, a calma será igual a 3 (a calma não diminuirá a partir do segundo grupo, porque Ghiaccio tapou os ouvidos ao passar).
E ao final do sexto segundo, a calma será igual a 3+1-3 = 1.
Além disso, sua calma nunca diminui.