400787: GYM100247 I Meteor Flow

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Meteor Flowtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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 ti and deal di 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.

Input

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: ti and di (1 ≤ ti, di ≤ 109) — the moment of time when i-th meteor will strike the ship and the damage it will deal. All ti are pairwise distinct and given in ascending order.

Output

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

ExamplesInput
3
3 2
5 4
6 3
Output
1
Input
5
1 2
3 2
5 3
6 2
7 3
Output
2

加入题单

上一题 下一题 算法标签: