Page not loading? Try clicking here.
Placeholder

#8408
Subtask

부케 3s 1024MB

Problems

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!


Input

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 ith line contains two integers l_i and r_i, representing the tulip protection constraints for tulip i.

[constraints]

  •  1 \leq N \leq 2 \cdot 10^5

  •  0 \leq l_i, r_i \leq N (i = 0,1,\ldots, N-1)


Output

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


Subtask

# Score Condition
#18

 l_i = r_i = l_j = r_j for all pairs (i, j)

#216

r_i = 0 for all i 

#328

N \leq 1000

#418

l_i, r_i \leq 2 for all i

#530

No additional constraints


Example #1

3
0 3
1 0
1 0
1

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.


Example #2

5
0 3
1 0
0 1
2 0
1 0
3

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.


Example #3

7
0 0
0 0
1 0
1 0
2 0
3 0
2 0
4

Example #4

6
2 2
2 2
2 2
2 2
2 2
2 2
2

Example #5

7
0 2
2 0
1 1
2 2
0 0
0 1
0 1
3


Source

EGOI(European Girls' Olympiad in Informatics) 2024 Day 1 B번

You must sign in to write code.