{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"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 \u003d 1 . . . n are some elements in N, and w0 \u003d 0.\r\u003cbr\u003eDefine set B \u003d {\u0026lt; x, y \u0026gt; | x, y ∈ R and there exists an index i \u0026gt; 0 such that 0 \u0026lt;\u003d y \u0026lt;\u003d hi ,∑\u003csub\u003e0\u0026lt;\u003dj\u0026lt;\u003di-1\u003c/sub\u003ewj \u0026lt;\u003d x \u0026lt;\u003d ∑\u003csub\u003e0\u0026lt;\u003dj\u0026lt;\u003di\u003c/sub\u003ewj}\r\u003cbr\u003eAgain, define set S \u003d {A| A \u003d WH for some W , H ∈ R\u003csup\u003e+\u003c/sup\u003e and there exists x0, y0 in N such that the set T \u003d { \u0026lt; x , y \u0026gt; | x, y ∈ R and x0 \u0026lt;\u003d x \u0026lt;\u003d x0 +W and y0 \u0026lt;\u003d y \u0026lt;\u003d y0 + H} is contained in set B}.\r\u003cbr\u003eYour mission now. What is Max(S)?\r\u003cbr\u003eWow, it looks like a terrible problem. Problems that appear to be terrible are sometimes actually easy.\r\u003cbr\u003eBut for this one, believe me, it\u0027s difficult."}},{"title":"Input","value":{"format":"HTML","content":"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 \u0026lt;\u003d n \u0026lt;\u003d 50000 and w\u003csub\u003e1\u003c/sub\u003eh\u003csub\u003e1\u003c/sub\u003e+w\u003csub\u003e2\u003c/sub\u003eh\u003csub\u003e2\u003c/sub\u003e+...+w\u003csub\u003en\u003c/sub\u003eh\u003csub\u003en\u003c/sub\u003e \u0026lt; 10\u003csup\u003e9\u003c/sup\u003e."}},{"title":"Output","value":{"format":"HTML","content":"Simply output Max(S) in a single line for each case."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n1 2\r\n3 4\r\n1 2\r\n3\r\n3 4\r\n1 2\r\n3 4\r\n-1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e12\r\n14\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}