题目描述

题目译自 European Girls' Olympiad in Informatics 2024 Day1 T2. Bouquet

在参观了世界最大的花卉园之一——荷兰库肯霍夫花园后，莉克深深爱上了花卉，决定在路边采摘一些郁金香，制作一束美丽的花束。然而，由于荷兰严格的郁金香保护法，你在采摘时必须遵守一些规则。

路边有一排 $N$ 株郁金香，编号从 $0$ 到 $N-1$，从左到右依次排列。郁金香保护法为每株郁金香 $i$ 指定了两个整数 $l_i$ 和 $r_i$。如果你选择了郁金香 $i$ 加入花束，那么紧邻其左侧的 $l_i$ 株郁金香和右侧的 $r_i$ 株郁金香不能同时被选入花束。注意，如果左侧少于 $l_i$ 株或右侧少于 $r_i$ 株郁金香，该侧的所有郁金香仍需被排除（允许溢出）。

你想知道，如果以最优方式采摘，你最多能采摘多少株郁金香。帮助莉克打造一束美丽的花束，找到这个问题的答案！

输入格式

第一行包含一个整数 $N$，表示路边郁金香的数量。

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

输出格式

输出一个整数，表示你在遵守保护法的前提下最多能采摘的郁金香数量。

3
0 3
1 0
1 0

1

在第一个样例中，如果采摘郁金香 $0$，你不能采摘右侧的两株郁金香。采摘郁金香 $1$ 不禁止采摘郁金香 $2$，但采摘郁金香 $2$ 会禁止采摘郁金香 $1$，因此你无法同时采摘这两株。所以，你最多能采摘 $1$ 株郁金香。

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

在第三个样例中，通过采摘郁金香 $0, 1, 3, 6$，你最多能获得 $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

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 2 \cdot 10^5$
• $0 \leq l_i, r_i \leq N$（对于 $i = 0, 1, \ldots, N-1$）

详细子任务附加限制及分值如下表所示。