题目描述

${FJ}$的奶牛们决定去度假，并奇迹般地找到了愿意卖票的航空公司。

然而，当他们到达机场并开始登机时，他们面临着一个有趣的问题。

这架飞机有${N }$个座位，我们将其建模为数轴上的点 ${x=1 }$到 ${x=N}$。

所有${N }$头奶牛 ${(1 <= N <= 200,000) }$都在排队等候坐下。牛 ${N }$位于位置 ${x=0，}$牛 ${N-1 }$位于位置 ${x=-1，}$依此类推。

奶牛 ${i }$已分配给座位 ${S_i，}$其中 ${S_1,...,S_N }$是 ${1,...,N }$的排列。

在每个时间步长，如果可以，每头牛都会向右走一步。当奶牛${i }$到达她的座位 ${S_i }$时，她会停下来将行李放入头顶行李箱，这需要 ${T_i }$秒，然后坐下。

对于那些 ${T_i }$步骤，她身后的母牛（如果有的话）被阻止向前移动。如果她身后有一排奶牛，那么这条线也被有效地挡住了。

所有的奶牛坐下需要多长时间？

所有奶牛的${T_i }$总和将小于 ${1,000,000,000}$。

想象一下飞机有${N}$个座位，${N}$个座位相当于数轴上的${1}$至${N}$共${N}$个整点，第${1}$个座位在整点${1}$处，第${2}$个座位在整点${2}$处，……第${N}$个座位在整点${N}$处。

有${N}$个奶牛排好队，要登陆坐飞机，第${N}$头奶牛在数轴的整点${0}$处，第${N?1}$头奶牛在数轴的整点?${1}$处，……第${1}$头奶牛在数轴的整点?

${N+1}$处。第${i}$头奶牛的座位号是${Si}$。注意：每头奶牛都有唯一的一个座位，不会出现多头奶牛有相同的座位号。

在每一秒钟，奶牛会向右移动一步到达下一个整点，前提是没有奶牛挡住它。当第${i}$头奶牛到达它的座位${Si}$时，它需要花费${Ti}$秒去把行李放到头顶的行李架上，然后坐到自己的位置上，在此过程中，由于飞机通道很窄，所以在第${i}$头奶牛 坐到自己座位之前，在它左边的所有奶牛都不能动，要等奶牛${i}$放好行李坐好后才能动。

现在的问题是，至少要多少秒之后，所有的奶牛都能做到自己的座位上？

输入格式

第${1 }$行：单个整数 ${N}$。

第${2..N+1 }$行：两个空格分隔的整数，${S_i }$和 ${T_i}$。

输出格式

第${1 }$行：单行表示让所有奶牛就座所需的时间。

样例

输入样例

3

2 5

3 10

1 5

输出样例

19

提示

最初，奶牛的位置是这样的：

奶牛${-> 123}$

${123 <- }$座位

奶牛${1 }$试图到达座位 ${2，}$奶牛 ${2 }$试图到达座位 ${3，}$奶牛 ${3 }$试图到达座位 ${1}$。

一步之后，他们都会将${1 }$向右移动，奶牛 ${3 }$会到达她的座位：

${123 123 }$奶牛 ${3 }$需要 ${5 }$秒才能坐下，此时她实际上消失了。

${12 123 }$奶牛 ${1 }$和 ${2 }$还需要 ${3 }$秒才能到达他们想要的座位：

${12 123 }$奶牛 ${1 }$坐下需要 ${5 }$秒，奶牛 ${2 }$坐下需要 ${10 }$秒，所以总共需要 ${10 }$秒。

总共花了${1 + 5 + 3 + 10 = 19 }$秒。