题目背景

Day 1 Problem B.

题面译自 EGOI2024 bouquet。翻译来自于 ChatGPT 并进行人工校对，若有误请联系 rui_er。

题目描述

参观了世界上最大的花园之一库肯霍夫后，Lieke 非常喜欢花，因此她决定收集一些路边生长的郁金香来制作一个漂亮的花束。然而，在收集花朵时，她必须遵守荷兰严格的郁金香保护法的一些规定。

沿着道路从左到右有 $N$ 株郁金香，编号从 $0$ 到 $N - 1$。郁金香保护法为郁金香 $i$ 分配了两个整数，$l_i$ 和 $r_i$。如果郁金香 $i$ 被包含在花束中，则郁金香 $i$ 左边紧邻的 $l_i$ 株郁金香和右边紧邻的 $r_i$ 株郁金香不能包含在花束中。注意，如果郁金香 $i$ 左边的郁金香少于 $l_i$ 株，或者右边的郁金香少于 $r_i$ 株，那么该侧所有的郁金香仍然不能包含在花束中（允许溢出）。

Lieke 想知道如果她最佳地选择花朵，最多能摘取多少株郁金香。帮她找到这个问题的答案，制作一个漂亮的花束吧！

输入格式

输入的第一行包含一个整数 $N$，表示沿路生长的郁金香数量。

接下来的 $N$ 行描述了郁金香保护法的信息：第 $i$ 行包含两个整数 $l_i$ 和 $r_i$，表示郁金香 $i$ 的保护限制。

输出格式

输出一个整数，表示 Lieke 在遵守保护法的情况下可以摘取的最大郁金香数量。

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

提示

样例解释

在第一个样例中，如果 Lieke 摘取郁金香 $0$，她不能摘取右边的两朵郁金香。摘取郁金香 $1$ 并不禁止她摘取郁金香 $2$，但郁金香 $2$ 禁止她摘取郁金香 $1$，因此她不能同时摘取它们。所以，Lieke 可以摘取的最大花朵数量是 $1$。

在第二个样例中，Lieke 可以摘取的郁金香数量最多是 $3$，获得此结果的方式如图所示。其他摘取郁金香的方式会导致更小的答案。

在第三个样例中，通过摘取郁金香 $0, 1, 3$ 和 $6$ 可以获得最多的 $4$ 朵郁金香。

数据范围

对于全部数据，$1\le N\le 2\times 10^5$，$0\le l_i,r_i\le N$。

• 子任务一（$8$ 分）：对于任意 $(i,j)$，$l_i=r_i=l_j=r_j$。
• 子任务二（$16$ 分）：$r_i=0$。
• 子任务三（$28$ 分）：$N\le 1000$。
• 子任务四（$18$ 分）：$l_i,r_i\le 2$。
• 子任务五（$30$ 分）：无特殊限制。

注：部分测试点在 EGOI 中被放在多个子任务中。为节省评测资源及整理数据的工作量，这些测试点被放在包含它的所有子任务中编号最小的一个。这可能导致一份代码得到比预期更高的分数，但是无法过题。