400787: GYM100247 I Meteor Flow

The spaceship «Enterprise» has got into meteor flow and is under threat of destruction. Once this happens, Captain Kirk ordered to switch the force shield on, and onboard computer instantly determined n meteors which give no chance to be evaded. Assuming the force shield is switched on at the moment 0, it is known that i-th meteor will strike the «Enterprise» at the moment t_i and deal d_i units of damage.

Each unit of time the force shield increases its power by 1. When the meteor strikes the «Enterprise», the ship receives damage if the power of the shield is less than the meteor's damage. Otherwise, the power of the force shield decreases by the meteor's damage.

The «Enterprise» has a cannon, each shot of which can knock any meteor off. But Captain Kirk does not like unnecessary firing and wants to overcome the meteor flow without any damage received and doing as few shots as possible.

The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of meteors.

Then n lines follow. Each of them contains two integers separated by space: t_i and d_i (1 ≤ t_i, d_i ≤ 10⁹) — the moment of time when i-th meteor will strike the ship and the damage it will deal. All t_i are pairwise distinct and given in ascending order.

Output a single integer — the minimal number of shots that needs to be done in order to not receive any damage.

3
3 2
5 4
6 3

1

5
1 2
3 2
5 3
6 2
7 3

2