您邀请 $$$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。