Bouquet

시간 제한3초메모리 제한1024 MB

요약

일렬로 놓인 튤립에서 i번째 튤립을 고르면 왼쪽 l_i개와 오른쪽 r_i개를 고를 수 없을 때, 고를 수 있는 튤립 개수의 최댓값을 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 배열, 그리디
정답자: 아직 제출이 없습니다

문제

After visiting Keukenhof, one of the world's largest flower gardens, Lieke became very fond of flowers, so she has decided to collect some tulips growing next to the road in order to build a beautiful bouquet. However, when collecting the flowers, she has to respect some rules due to the strict tulip protection laws in the Netherlands.

There are $N$ tulips numbered from $0$ to $N-1$ growing in a line along the road, in order from left to right. The tulip protection law assigns two integers, $l\_i$ and $r\_i$ , to tulip $i$ . In case tulip $i$ is included in the bouquet, the $l\_i$ tulips immediately to the left of tulip $i$ and the $r\_i$ tulips immediately to the right of tulip $i$ cannot also be in the bouquet. Note that if there are fewer than $l\_i$ tulips to the left or fewer than $r\_i$ tulips to the right of tulip $i$ , then all tulips from that side are still excluded from the bouquet (overflows are allowed).

Lieke wonders what the maximum number of tulips she can pick is if she picks her flowers optimally. Help her build a beautiful bouquet by finding the answer to her question!

입력

The first line of input contains a single integer $N$ , the number of tulips growing along the road.

The following $N$ lines describe the information of the tulip protection law: the $i$ th line contains two integers $l\_i$ and $r\_i$ , representing the tulip protection constraints for tulip $i$ .

출력

Output a single integer, the maximum number of tulips Lieke can pick while respecting the protection law.

제한

$1 \leq N \leq 2 \cdot 10^5$ .
$0 \leq l\_i, r\_i \leq N$ for $i = 0,1,\ldots, N-1$ .

힌트

Note that some of the samples are not valid input for all test groups.

In the first sample, if Lieke picks tulip $0$ , she cannot pick the two tulips on the right. Picking tulip $1$ does not prohibit her from picking tulip $2$ , but tulip $2$ prohibits her from picking tulip $1$ , thus she cannot pick both of them. So, the maximum number of flowers Lieke can pick is $1$ .

In the second sample, the maximum possible number of tulips Lieke can pick is $3$ and the way it can be obtained is shown in the picture. Other ways of picking tulips result in a smaller answer.

예제5

예제 1
입력
```
3
0 3
1 0
1 0
```
예상 출력
```
1
```
예제 2
입력
```
5
0 3
1 0
0 1
2 0
1 0
```
예상 출력
```
3
```
예제 3
입력
```
7
0 0
0 0
1 0
1 0
2 0
3 0
2 0
```
예상 출력
```
4
```
예제 4
입력
```
6
2 2
2 2
2 2
2 2
2 2
2 2
```
예상 출력
```
2
```
예제 5
입력
```
7
0 2
2 0
1 1
2 2
0 0
0 1
0 1
```
예상 출력
```
3
```