﻿ Fuzhou University OnlineJudge ﻿
Problem 1305 Terrible Sets

## Problem Description

Let N be the set of all natural numbers {0,1,2,...}, and R be the set of all real numbers. wi,hi for i=1...n are some elements in N, and w0=0.
Define set B={<x,y>|x,y in R and there exists an index i>0 such that 0<=y<hi}

Again, define set S={A|A=WH for some W,H in R+ and there exists x0, y0 in N such that the set T={<x,y>|x,y in R and x0<=x<=x0+W and y0<=y<=y0+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 wi and hi 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 w1h1+w2h2+...+wnhn<10^9.

## Output

Simply output Max(S) in a single line for each case.

## Sample Input

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

12 14

## Source

Shanghai2004 Preliminary

Submit  Back  Status  Discuss
﻿