题目翻译

描述：

设$N$为所有自然数的集合{$0$, $1$, $2$, ...}，$R$为所有实数的集合。对于$i$ = $1$ ... $n$，$w$$_i$和$h$$_i$是$N$中的一些元素，且$w$$_0$ = $0$。

定义集合$B$ = {<$x$, $y$> | $x$, $y$ ∈ $R$，且存在一个索引$i$ > $0$，使得$0$ ≤ $y$ ≤ $h$$_i$，且∑($0$≤$j$≤$i-1$)$w$$_j$ ≤ $x$ ≤ ∑($0$≤$j$≤$i$)$w$$_j$}。

再次定义集合$S$ = {$A$ | $A$ = $W$ × $H$，其中$W$, $H$ ∈ $R+$，且存在$x$$_0$, $y$$_0$ ∈ $N$，使得集合$T$ = {<$x$, $y$> | $x$, $y$ ∈ $R$且$x$$_0$ ≤ $x$ ≤ $x$$_0$ + $W$且$y$$_0$ ≤ $y$ ≤ $y$$_0$ + $H$}包含于集合$B$}。

你的任务是求出Max($S$)。

看起来这是一个相当复杂的问题。看似复杂的问题有时其实很简单。但对于这个问题，相信我，它确实很难。

输入：

输入包含多个测试用例。每个测试用例的第一行给出一个整数$n$，随后$n$行每行给出$w$$_i$和$h$$_i$，用空格分隔。输入的最后一行是一个单独的整数$-1$，表示输入结束。你可以假设$1$ ≤ $n$ ≤ $50000$，且$w$$_1$$h$$_1$ + $w$$_2$$h$$_2$ + ... + $w$$_n$$h$$_n$ < $10^9$。

输出：

对于每个测试用例，简单地在一行中输出Max(S)。

示例输入：

3
1 2
3 4
1 2
3
3 4
1 2
3 4
-1

示例输出：

12
14

来源：

Shanghai 2004 Preliminary