题目描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

输入格式

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

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

输出格式

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

样例

输入样例

3

2 5

3 10

1 5

输出样例

19

提示

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

奶牛$\red{-> 123}$

$\red{123 <- }$座位

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

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

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

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

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

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