14001400 SUSTech Online Judge
Problem 1400 --Skylar's Job

1400: Skylar's Job

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 102  Solved: 33
[Submit][Status][Web Board]

Description

Skylar is doing a part-time job recently. She needs to put up the posters on the billboards in SUSTech. All the billboards, one by one, form a long chain of different width and height. The posters are rectangular and they cannot overlap. Naturally, posters can have common points on the sides. Every poster should exactly cover the surface of the billboards and the whole area of billboards has to be covered. Skylar wants to minimize her workload, so she ask you to help her calculate the minimum number of required posters.

Input

The first line contains an integer \(n(1 \leq n \leq 250000)\), denoting the number of billboards.

Each of the following \(n\) lines contains two integers \(w_i\) and \(h_i(1 \leq w_j,\ h_i \leq 10^9)\), seperated by a single space, denoting the width and height of the \(i_{th}\) billboard.

Output

One line an integer, denoting the minimum number of required posters.

Sample Input

5
1 2
1 3
2 2
2 5
1 4

Sample Output

4

HINT

Source

 

[Submit][Status]