您仍然拥有有关历史性足球比赛期间比分的部分信息。给您一组 $$$(a_i, b_i)$$$,表示在比赛期间的某个时刻得分为“$$$a_i$$$: $$$b_i$$$”。已知如果当前得分为“$$$x$$$:$$$y$$$»,则进球后得分将变为“$$$x+1$$$:$$$y$$$”或“$$$x$$$:$$$y+1$$$”。记分牌上平局最多出现多少次?
“$$$a_i$$$:$$$b_i$$$”对按时间顺序给出(时间增加),但您仅在某些时刻获得分数。最后一对对应于比赛的结束。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10000$$$) — 比赛中已知时刻的数量。
接下来的$$$n$$$行中的每一行都包含整数$$$a_i$$$和$$$b_i$$$($$$0 \le a_i, b_i \le 10^9$$$),表示该时刻比赛的得分(即第一队的进球数和第二队的进球数)。
所有矩均按时间顺序给出,即序列 $$$x_i$$$ 和 $$$y_j$$$ 是非递减的。最后得分表示比赛的最终结果。
输出
打印比分平局的最大时刻数。比赛开始时刻(比分 0:0)也计算在内。
示例
输入 #1
3 2 0 3 1 3 4
输出 #1
2
输入 #2
3 0 0 0 0 0 0
输出 #2
1
输入 #3
1 5 4
输出 #3
5
注意
在该示例中,导致最大平局次数的可能得分序列之一如下:0:0、1:0、2:0、2:1、3:1、3:2、3:3、3:4。