Stacking horizontal blocks

Time limit1sMemory limit512 MB

Summary

Drop N horizontal blocks one by one at fixed positions, each landing on the tallest surface below it, and report the final stack height.

Level: Medium7 of 10
Topics: Segment tree, Binary search, Prefix sum, Implementation
Solved: No attempts yet

Problem

You are going to play a game of Tetris in which only horizontal blocks appear. A total of $N$ horizontal blocks will appear, numbered $1, 2, \dots, N$ in the order they appear. Block $i$ has height $1$ and width $W_i$ . Block $i$ must be dropped at a distance of $D_i$ from the left wall. Rotating a block or moving its position is not possible.

A block falls from above, moving down one unit at a time until it hits another block or the floor. Given the information for the $N$ blocks, find the height of the stack.

Input

The first line gives the number of blocks $N$ ( $1 \le N \le 100{,}000$ ). Each of the next $N$ lines gives the information $W_i, D_i$ ( $1 \le W_i, D_i \le 1{,}000{,}000{,}000$ ) for one block, from block $1$ to block $N$ in order.

Output

Print the height of the stack after all blocks have been placed.

Examples2

Example 1
Input
```
5
4 2
4 6
4 5
3 1
3 3
```
Expected output
```
3
```
Example 2
Input
```
5
4 2
3 1
3 3
4 5
4 6
```
Expected output
```
5
```