题目描述
小 D 要安排 n 个人坐成若干个圆圈。每个人坐一把椅子,圆圈的其余位置放空椅子。
第 i 个人希望自己紧邻的左边一段至少有 Li 张空椅子,紧邻的右边一段至少有 Ri 张空椅子(自己坐的椅子不计入)。
相邻两个人的空椅子可以共用:前一个人的右边就是后一个人的左边。也就是说,如果第 i 个人紧挨在第 j 个人的右边,那么两人之间的空椅段是第 j 个人的右边和第 i 个人的左边,必须同时满足 Rj 和 Li。
如果一个人单独坐成一个圆圈,那么他左右两边其实是同一段空椅子,这段空椅子必须至少有 Li 和 Ri 中较大的那个数,即 max(Li,Ri) 张。
请你求出最少需要准备多少张椅子(包括每个人自己坐的 n 张椅子)。
输入格式
第一行一个整数 n。
接下来 n 行,每行两个整数 Li,Ri。
输出格式
输出一行一个整数,表示最少需要的椅子总数。
样例
3
1 1
1 1
1 1
6
1
5 6
7
4
1 2
2 1
3 5
5 3
15
样例解释
样例 1 中,三个人围成一圈,每两人之间放 1 张空椅子,共用 3 张空椅子,加上三个人自己的椅子,共 6 张。
样例 2 中,只有一个人,左右两边是同一段空椅子,需要 max(5,6)=6 张空椅子,加上自己的椅子,共 7 张。
样例 3 中,可以让第 1,2 个人围成一圈:从第 1 个人到第 2 个人需要 max(R1,L2)=max(2,2)=2 张空椅,从第 2 个人回到第 1 个人需要 max(R2,L1)=max(1,1)=1 张;再让第 3,4 个人围成一圈:两段分别需要 max(R3,L4)=max(5,5)=5 张和 max(R4,L3)=max(3,3)=3 张。空椅共 2+1+5+3=11 张,再加 4 张自己的椅子,共 15 张。
另一方面,每个人左边的那段空椅都必须至少满足他的 Li,所以空椅总数至少是 L1+L2+L3+L4=1+2+3+5=11。上面的安排正好用了 11 张空椅,因此 15 张就是最少的。
数据范围与约定
| 子任务 |
分值 |
限制 |
| 1 |
30 |
1≤n≤10 |
| 2 |
70 |
1≤n≤105 |
对于 100% 的数据,保证 1≤n≤105,1≤Li,Ri≤109。
答案可能超过 32 位整数范围,请使用 long long 类型。