CF1060D Social Circles

你邀请了 $n$ 位客人来参加晚宴！你计划安排一个或多个圆形的椅子圈。每把椅子要么被一位客人占用，要么是空的。你可以设置任意数量的椅子圈。 你的客人们有些害羞，第 $i$ 位客人希望他的椅子左边至少有 $l_i$ 把空椅子，右边至少有 $r_i$ 把空椅子。这里的“左”和“右”是指所有客人都面向圆心时的方向。注意，如果某位客人所在的圈里只有他一个人，那么他左边的 $l_i$ 把椅子和右边的 $r_i$ 把椅子可以重叠。 你需要使用的椅子总数最少是多少？

第一行包含一个整数 $n$，表示客人的数量，$(1 \leqslant n \leqslant 10^5)$。 接下来的 $n$ 行，每行包含两个用空格分隔的整数 $l_i$ 和 $r_i$，$(0 \leqslant l_i, r_i \leqslant 10^9)$。

输出一个整数，表示你需要使用的最少椅子数。

在第二个样例中，唯一的最优方案是使用两个圈：一个有 $5$ 把椅子的圈，容纳第 $1$ 和第 $2$ 位客人；另一个有 $10$ 把椅子的圈，容纳第 $3$ 和第 $4$ 位客人。 在第三个样例中，只有一个圈，且只有一个人。该客人希望左边至少有 $5$ 把空椅子，右边至少有 $6$ 把空椅子。由于圈内只有他一人，这两部分可以重叠，因此总椅子数至少为 $6+1=7$。 由 ChatGPT 4.1 翻译