Problem Background

Day 1 Problem B.

The problem statement is translated from EGOI2024 bouquet. The translation was done using ChatGPT and manually proofread. If there are any errors, please contact rui_er.

Problem Description

After visiting one of the world's largest gardens, Keukenhof, Lieke fell in love with flowers and decided to collect some tulips growing by the roadside to make a beautiful bouquet. However, she must adhere to some strict regulations of the Dutch tulip protection laws while collecting the flowers.

There are $N$ tulips along the road from left to right, numbered from $0$ to $N - 1$. The tulip protection laws assign two integers, $l_i$ and $r_i$, to tulip $i$. If tulip $i$ is included in the bouquet, then the $l_i$ tulips immediately to the left of tulip $i$ and the $r_i$ tulips immediately to the right of tulip $i$ cannot be included in the bouquet. Note that if there are fewer than $l_i$ tulips to the left of tulip $i$, or fewer than $r_i$ tulips to the right, all tulips on that side still cannot be included in the bouquet (overflow is allowed).

Lieke wants to know the maximum number of tulips she can pick if she chooses the flowers optimally. Help her find the answer to this problem and create a beautiful bouquet!

Input Format

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

The next $N$ lines describe the information of the tulip protection laws: the $i$-th line contains two integers $l_i$ and $r_i$, representing the protection limits for tulip $i$.

Output Format

Output a single integer, the maximum number of tulips Lieke can pick while adhering to the protection laws.

Sample Input and Output

Sample Input #1

3
0 3
1 0
1 0

Sample Output #1

1

Sample Input #2

5
0 3
1 0
0 1
2 0
1 0

Sample Output #2

3

Sample Input #3

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

Sample Output #3

4

Sample Input #4

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

Sample Output #4

2

Sample Input #5

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

Sample Output #5

3

Notes

Sample Explanation

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

In the second sample, the maximum number of tulips Lieke can pick is $3$, as shown in the figure. Other ways of picking tulips would result in a smaller answer.

In the third sample, the maximum number of tulips, $4$, can be achieved by picking tulips $0, 1, 3,$ and $6$.

Data Range

For all data, $1 \le N \le 2 \times 10^5$, $0 \le l_i, r_i \le N$.

• Subtask 1 (8 points): For any $(i, j)$, $l_i = r_i = l_j = r_j$.
• Subtask 2 (16 points): $r_i = 0$.
• Subtask 3 (28 points): $N \le 1000$.
• Subtask 4 (18 points): $l_i, r_i \le 2$.
• Subtask 5 (30 points): No additional constraints.

Note: Some test cases were placed in multiple subtasks during EGOI. To save evaluation resources and simplify data management, these test cases were placed in the subtask with the smallest number that includes them. This may result in a higher score than expected for a single submission, but it does not allow for a full solution.

见题面 Input 部分

见题面 Output 部分