Description

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

有 $N$ 个奶牛排好队要登机，第 $N$ 头奶牛在数轴的整点 $0$ 处，第 $N−1$ 头奶牛在数轴的整点 $−1$ 处，……，第 $1$ 头奶牛在数轴的整点 $−N+1$ 处。第 $i$ 头奶牛的座位号是 $S_i$。注意：每头奶牛都有唯一的一个座位，不会出现多头奶牛有相同的座位号。

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

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

Input Format

第一行：一个整数 $N (1 \le N \le 2 \times 10^5)$。

第 $2$ 行到第 $N+1$ 行：每行两个整数 $S_i, T_i$。

保证 $S_1 \sim S_n$ 是 $1 \sim n$ 的排列，所有 $T_i$ 之和 $\le 10^9$。

Output Format

一行一个整数，表示使所有的奶牛都能做到自己的座位上的最短时间。

3 
2 5 
3 10 
1 5 

19