P2897 [USACO08JAN] Artificial Lake G

USACO 2008 January Gold

The oppressively hot summer days have raised the cows' clamoring to its highest level. Farmer John has finally decided to build an artificial lake. For his engineering studies, he is modeling the lake as a two-dimensional landscape consisting of a contiguous sequence of N soon-to-be-submerged levels (1 ≤ N ≤ 100,000) conveniently numbered 1..N from left to right. Each level i is described by two integers, its width Wi (1 ≤ Wi ≤ 1,000) and height (like a relative elevation) Hi (1 ≤ Hi ≤ 1,000,000). The heights of FJ's levels are unique. An infinitely tall barrier encloses the lake's model on the left and right. One example lake profile is shown below. ```plain * * : * * : * * 8 * *** * 7 * *** * 6 * *** * 5 * ********** 4

* Line 1: A single integer: N * Lines 2..N+1: Line i+1 describes level i with two space-separated integers: Wi and Hi

Lines 1..N: Line i contains a single integer that is the number of minutes that since sunrise when level #i is covered by water of height 1.