Artificial Lake

On the hottest summer days, Farmer John decides to build an artificial lake. He models the lake as a two-dimensional landscape: a contiguous row of $N$ platforms numbered $1 \dots N$ from left to right ($1 \le N \le 100{,}000$).

Platform $i$ is described by two integers: its width $W_i$ ($1 \le W_i \le 1{,}000$) and its height (a relative elevation) $H_i$ ($1 \le H_i \le 1{,}000{,}000$). All heights are distinct. Infinitely tall walls enclose the landscape on the left and the right. One example landscape profile is shown below.

         *            *  :
         *             *  :
         *             *  8
         *    ***      *  7
         *    ***      *  6
         *    ***      *  5
         *    **********  4 <- height
         *    **********  3
         ***************  2
         ***************  1
Level    |  1 |2|  3   |

Water pours into the bottom of the lowest platform at a rate of $1$ square unit per minute. The water falls straight down until it lands on something, and then it spreads out sideways as water always does. Assume that both the falling and the spreading happen instantly.

For each platform, determine the number of minutes after sunrise at which it first becomes covered by a layer of water exactly $1$ unit tall.

     WATER              WATER OVERFLOWS
       |                       |
     * |          *      *     |      *      *            *
     * V          *      *     V      *      *            *
     *            *      *    ....    *      *~~~~~~~~~~~~*
     *    **      *      *~~~~** :    *      *~~~~**~~~~~~*
     *    **      *      *~~~~** :    *      *~~~~**~~~~~~*
     *    **      *      *~~~~**~~~~~~*      *~~~~**~~~~~~*
     *    *********      *~~~~*********      *~~~~*********
     *~~~~*********      *~~~~*********      *~~~~*********
     **************      **************      **************
     **************      **************      **************

     After 4 mins        After 26 mins       After 50 mins
     Lvl 1 submerged     Lvl 3 submerged     Lvl 2 submerged

Note: the answer will not always fit in 32 bits.

• Line 1: a single integer $N$.
• Lines 2 to $N+1$: line $i+1$ describes platform $i$ with two space-separated integers, $W_i$ and $H_i$.

• Lines 1 to $N$: line $i$ contains a single integer, the number of minutes after sunrise at which platform $i$ is first covered by a $1$-unit-tall layer of water.