P2897 [USACO08JAN] Artificial Lake G

USACO 2008 January Gold

夏日那让人喘不过气的酷热将奶牛们的烦躁情绪推到了最高点。最终，FJ 决定建一个人工湖供奶牛消暑之用。为了使湖看起来更加真实，FJ 决定将湖的横截面建成 $N(1\le N\le 100,000)$ 个连续的平台高低错落的组合状，所有的平台从左到右按 $1\sim N$ 依次编号。当然咯，在湖中注入水后，这些平台都将被淹没。平台 $i$ 在设计图上用它的宽度 $W_i(1\le W_i\le1,000)$ 和高度（你可以理解为该平台顶离 FJ 挖的地基的高度）$H_i(1\le H_i\le 1,000,000)$ 来描述的。所有平台的高度都是独一无二的。湖的边缘可以视为无限高的平台。下面给出了一张 FJ 的设计图： ```plain * * : * * : * * 8 * *** * 7 * *** * 6 * *** * 5 * ********** 4

第一行一个正整数 $N$。 下面 $N$ 行，每行两个正整数 $W_i,H_i$。

$N$ 行，每行一个正整数，表示：对于每一个平台，它的顶部是从哪个时刻开始，与水面的距离至少为 $1$ 单位长度。