[Usaco2008 Jan]人工湖

炎热的夏日令奶牛们烦躁不安，约翰决定修建一个人工湖供奶牛消暑。为了使人工湖看起来更加自然，湖的横截面由 $N$ 个高低错落且连续的平台组成，所有平台从左到右依次编号为 $1$ 到 $N$ 。注水完成后，所有平台都将被淹没。

平台 $i$ 由宽度 $W_i$ 和高度 $H_i$ 描述，其中高度是指平台顶部到湖底地基的距离。所有平台的高度互不相同，湖的左右边缘可以视为无限高的平台。

湖坑挖好后，约翰会在高度最低的平台上方，以每分钟 $1$ 单位体积的速度向湖中注水。水离开水管后会立即下落，直到接触平台顶部或此前注入的水，随后迅速流动并扩散。为简化问题，可以认为水的下落、流动和扩散都是瞬间完成的。

对于每个平台，请求出从开始注水起，经过多长时间后，该平台顶部与水面的距离首次达到至少 $1$ 单位。答案可能超出 $32$ 位整数的表示范围。

输入格式

第一行包含一个整数 $N$ ，表示平台数量。

接下来 $N$ 行，第 $i$ 行包含两个以空格分隔的整数 $W_i$ 和 $H_i$ ，分别表示平台 $i$ 的宽度和高度。

输出 $N$ 行，第 $i$ 行包含一个整数，表示平台 $i$ 的顶部与水面的距离首次达到至少 $1$ 单位时，已经经过的分钟数。

4
50
26

最低的平台是平台 $1$ ，因此约翰从平台 $1$ 的上方开始注水。

注水 $4$ 分钟后，平台 $1$ 顶部与水面的距离达到 $1$ 单位；注水 $26$ 分钟后，平台 $3$ 满足条件；注水 $50$ 分钟后，平台 $2$ 满足条件。

本题为 USACO 2008 January 试题「人工湖」，题面与测试数据整理自 BZOJ。

4
50
26