Background

Day 1 Problem B.

This statement is translated from EGOI2024 bouquet. The translation comes from ChatGPT and has been manually proofread. If there are any mistakes, please contact rui_er.

Problem Description

After visiting one of the largest gardens in the world, Keukenhof, Lieke fell in love with flowers, so she decided to pick some tulips growing by the roadside to make a beautiful bouquet. However, while picking flowers, she must follow some rules from the strict Dutch tulip protection law.

Along the road from left to right there are $N$ tulips, numbered from $0$ to $N - 1$. The tulip protection law assigns 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, then all tulips on that side still cannot be included in the bouquet (overflow is allowed).

Lieke wants to know, if she chooses flowers optimally, what is the maximum number of tulips she can pick. Help her find the answer and make a beautiful bouquet!

Input Format

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

The next $N$ lines describe the tulip protection law: line $i$ contains two integers $l_i$ and $r_i$, representing the protection constraints of tulip $i$.

Output Format

Output one integer, the maximum number of tulips Lieke can pick while following the protection law.

3
0 3
1 0
1 0

1

5
0 3
1 0
0 1
2 0
1 0

3

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

4

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

2

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

3

Hint

Sample Explanation

In the first sample, if Lieke picks tulip $0$, she cannot pick the two tulips on its right. Picking tulip $1$ does not forbid her from picking tulip $2$, but tulip $2$ forbids her from picking tulip $1$, so she cannot pick both of them at the same time. Therefore, the maximum number of flowers Lieke can pick is $1$.

In the second sample, Lieke can pick at most $3$ tulips, and one way to achieve this is shown in the figure. Other ways of picking tulips lead to a smaller answer.

In the third sample, picking tulips $0, 1, 3$ and $6$ gives the maximum of $4$ tulips.

Constraints

For all testdata, $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 special constraints.

Note: Some test points were placed into multiple subtasks in EGOI. To save judging resources and reduce the workload of organizing the data, these test points are placed into the subtask with the smallest index among all subtasks that contain them. This may cause a solution to get a higher score than expected, but still fail to pass the problem.

Translated by ChatGPT 5