
ZOJ Problem Set  2422
Let N be the set of all natural numbers {0, 1, 2, ... }, and R be the set of all real numbers. w_{i}, h_{i} for i = 1 ... n are some elements in N, and w_{0} = 0. Define set B = { <x, y>  x, y R and there exists an index i > 0 such that 0 <= y <= h_{i}, } Again, define set S = {A  A = WH for some W, H R^{+} and there exists x_{0}, y_{0} in N such that the set T = { <x, y>  x, y R and x_{0} <= x <= x_{0} + W and y_{0} <= y <= y_{0} + H} is contained in set B}. Your mission now. What is Max(S)? Wow, it looks like a terrible problem. Problems that appear to be terrible are sometimes actually easy. But for this one, believe me, it's difficult. Input The input consists of several test cases. For each case, n is given in a single line, and then followed by n lines, each containing w_{i} and h_{i} separated by a single space. The last line of the input is an single integer 1, indicating the end of input. You may assume that 1 <= n <= 50000 and w_{1}h_{1}+w_{2}h_{2}+...+w_{n}h_{n} < 10^{9}. Output Simply output Max(S) in a single line for each case. Sample Input
3 Sample Output
12 Source: Asia 2004, Shanghai (Mainland China), Preliminary 