33OJ
登录 注册

#D1040. 椅子

椅子

题目描述

小 D 要安排 nn 个人坐成若干个圆圈。每个人坐一把椅子,圆圈的其余位置放空椅子。

第 ii 个人希望自己紧邻的左边一段至少有 LiL_i 张空椅子,紧邻的右边一段至少有 RiR_i 张空椅子(自己坐的椅子不计入)。

相邻两个人的空椅子可以共用:前一个人的右边就是后一个人的左边。也就是说,如果第 ii 个人紧挨在第 jj 个人的右边,那么两人之间的空椅段是第 jj 个人的右边和第 ii 个人的左边,必须同时满足 RjR_j 和 LiL_i。

如果一个人单独坐成一个圆圈,那么他左右两边其实是同一段空椅子,这段空椅子必须至少有 LiL_i 和 RiR_i 中较大的那个数,即 max⁡(Li,Ri)\max(L_i,R_i) 张。

请你求出最少需要准备多少张椅子(包括每个人自己坐的 nn 张椅子)。

输入格式

第一行一个整数 nn。

接下来 nn 行,每行两个整数 Li,RiL_i,R_i。

输出格式

输出一行一个整数,表示最少需要的椅子总数。

样例

3
1 1
1 1
1 1
6
1
5 6
7
4
1 2
2 1
3 5
5 3
15

样例解释

样例 1 中,三个人围成一圈,每两人之间放 11 张空椅子,共用 33 张空椅子,加上三个人自己的椅子,共 66 张。

样例 2 中,只有一个人,左右两边是同一段空椅子,需要 max⁡(5,6)=6\max(5,6)=6 张空椅子,加上自己的椅子,共 77 张。

样例 3 中,可以让第 1,21,2 个人围成一圈:从第 11 个人到第 22 个人需要 max⁡(R1,L2)=max⁡(2,2)=2\max(R_1,L_2)=\max(2,2)=2 张空椅,从第 22 个人回到第 11 个人需要 max⁡(R2,L1)=max⁡(1,1)=1\max(R_2,L_1)=\max(1,1)=1 张;再让第 3,43,4 个人围成一圈:两段分别需要 max⁡(R3,L4)=max⁡(5,5)=5\max(R_3,L_4)=\max(5,5)=5 张和 max⁡(R4,L3)=max⁡(3,3)=3\max(R_4,L_3)=\max(3,3)=3 张。空椅共 2+1+5+3=112+1+5+3=11 张,再加 44 张自己的椅子,共 1515 张。

另一方面,每个人左边的那段空椅都必须至少满足他的 LiL_i,所以空椅总数至少是 L1+L2+L3+L4=1+2+3+5=11L_1+L_2+L_3+L_4=1+2+3+5=11。上面的安排正好用了 1111 张空椅,因此 1515 张就是最少的。

数据范围与约定

子任务 分值 限制
11 3030 1≤n≤101 \le n \le 10
22 7070 1≤n≤1051 \le n \le 10^5

对于 100%100\% 的数据,保证 1≤n≤1051 \le n \le 10^5,1≤Li,Ri≤1091 \le L_i,R_i \le 10^9。

答案可能超过 32 位整数范围,请使用 long long 类型。