← 返回题目列表

Codeforces · 1060/D

D. 社交圈

中文机器翻译题面 查看原题

您邀请 $$$n$$$ 客人共进晚餐!您计划布置一圈或多圈椅子。每张椅子要么被一位客人占用,要么空着。您可以制作任意数量的圆圈。

您的客人碰巧有点害羞,因此第 $$$i$$$ 位客人希望在他的椅子左边至少有 $$$l_i$$$ 个空闲椅子,在右边至少有 $$$r_i$$$ 个空闲椅子。选择“左”和“右”方向时假设所有客人都将坐在朝向圆圈中心的位置。请注意,当一位客人是他的圈子中唯一的客人时,他左边的 $$$l_i$$$ 椅子和他右边的 $$$r_i$$$ 椅子可能会重叠。

您必须使用的椅子总数最少是多少?

输入

第一行包含一个整数 $$$n$$$ — 客人数量,($$$1 \leqslant n \leqslant 10^5$$$)。

接下来的 $$$n$$$ 行包含 $$$n$$$ 空格分隔的整数对 $$$l_i$$$ 和 $$$r_i$$$ ($$$0 \leqslant l_i, r_i \leqslant 10^9$$$)。

输出

输出一个整数——您必须使用的最小椅子数量。

示例

输入 #1

3
1 1
1 1
1 1

输出 #1

6

输入 #2

4
1 2
2 1
3 5
5 3

输出 #2

15

输入 #3

1
5 6

输出 #3

7

注意

在第二个样本中,唯一的最佳答案是使用两个圆圈:一个圆圈有 $$$5$$$ 椅子,可容纳客人 $$$1$$$ 和 $$$2$$$,另一个圆圈有 $$$10$$$ 椅子,可容纳客人 $$$3$$$ 和 $$$4$$$。

在第三个示例中,只有一个圈子和一个人。客人的左边应该至少有五张空闲椅子,右边至少有六张空闲椅子可供下一个人使用,在这种情况下是客人本人。因此,椅子总数至少应为 6+1=7。