water1

Time Limit: 1000MS

Memory Limit: 65536KB

Description

听说全球气候变暖,冰川融化,海水淹大地。着实好奇要融化多少冰川会淹没我的宿舍,哦不,淹没南京,反正NJUST应该总会是第一批被淹的。 现将问题简化成一个二维坐标系的模型。有N个矩形块区域,每个区域有海拔(H)和宽度(W),区域按照顺序给出,比如有3个区域,第一个区域宽度为1,海拔为2,第二个区域宽度为5,海拔为6,第三个区域宽度为3,海拔为4,从图像上看就是像这样:(Y轴是海拔) 8 7 6 +++++ 5 +++++ 4 ++++++++ 3 ++++++++ 2 +++++++++ 1 +++++++++ 123456789 假设最左边和最右边都是无限高的墙。 为了简化问题,假设水流下来的速度是每秒一个单位的水,并且总是往区域一降水(某沿海地区)。 现在请问要淹没所有的区域至少要多少时间(秒)?淹没的定义是,所有的区域表面至少覆盖一层水。如果没有区域则至少要放一滴水。 上图例子中,淹没完如下: 8 7 wwwwwwwww 6 w+++++www 5 w+++++www 4 w++++++++ 3 w++++++++ 2 +++++++++ 1 +++++++++ 123456789 所以需要19秒。

Input

多CASE,测试数据以EOF结尾,对于每个CASE: 第一行一个整数N(0 <= N <= 10^5)。 接下去N行每行对应两个整数H(1 <= H <= 10^5),W(1 <= W <= 10^5)分别对应第N个区域的海拔和宽度。

Output

一个整数,表示所需要的时间。

Sample Input

3
2 1 
6 5
4 3

Sample Output

19

Hint

None

Source

None

提交代码