인공 호수

무더운 여름날, 농부 존은 인공 호수를 만들기로 합니다. 그는 호수를 2차원 지형으로 모델링합니다. 지형은 왼쪽에서 오른쪽으로 $1 \dots N$번까지 번호가 매겨진, 서로 맞닿은 $N$개의 판으로 이루어져 있습니다 ($1 \le N \le 100{,}000$).

$i$번 판은 두 정수로 표현됩니다. 하나는 너비 $W_i$ ($1 \le W_i \le 1{,}000$)이고, 다른 하나는 높이(상대 고도) $H_i$ ($1 \le H_i \le 1{,}000{,}000$)입니다. 모든 판의 높이는 서로 다릅니다. 지형의 왼쪽과 오른쪽은 무한히 높은 벽으로 막혀 있습니다. 아래는 지형의 한 예시입니다.

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

물은 가장 낮은 판의 바닥으로 1분에 $1$ 제곱 단위씩 부어집니다. 물은 무언가에 닿을 때까지 곧장 아래로 떨어진 뒤, 물이 늘 그러하듯 옆으로 퍼져 나갑니다. 떨어지는 것과 퍼지는 것은 모두 순식간에 일어난다고 가정합니다.

각 판에 대해, 그 판이 높이 정확히 $1$짜리 물층으로 처음 덮이는 시각(해가 뜬 뒤 지난 분)을 구하세요.

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

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

참고: 답이 항상 32비트에 들어가는 것은 아닙니다.

• 첫째 줄: 정수 $N$.
• 둘째 줄부터 $N+1$번째 줄까지: $i+1$번째 줄에는 $i$번 판을 나타내는 두 정수 $W_i$와 $H_i$가 공백으로 구분되어 주어집니다.

• 첫째 줄부터 $N$번째 줄까지: $i$번째 줄에는 $i$번 판이 높이 $1$짜리 물층으로 처음 덮이는, 해가 뜬 뒤 지난 시간(분)을 정수 하나로 출력합니다.