TopCoder

Thumb output jddoia
$\huge 南ことり$
今天也要輸贏!?

User's AC Ratio

94.1% (16/17)

Submission's AC Ratio

33.7% (34/101)

Description

在一個「漸進式框架」當中,你想要找到一個最大面積的矩形位置放置你最喜愛的一幅畫。

當然地,畫框必須掛正,所以矩形的四個邊都必須與框架的邊平行或垂直。

所謂的「漸進式框架」,指的是任何一個水平線截出的框架區段是連續,並且由上往下該區段只會往右移動,如下圖。

Input Format

第一列有一個正整數$n$ ($n\leq 100,000$),代表從框架左上角開始,往右、往下、往右、...總共有幾條邊。
第$2~n+1$列總共有$n$個正整數,依序代表往右、往下、...的每邊邊長。
第$n+2$列有一個正整數$m$ ($m\leq 100,000$),代表從框架左上角開始,往下、往右、往下、...總共有幾條邊。
第$n+3~n+m+2$列有總共有$m$個正整數,依序代表往下、往右、...的每邊邊長。

你可以假設輸入的框架一定是正確的,而且畫框形成的多邊形不會自交、$n,m$都是偶數。
所有數字都不超過$10^ 9 $。

Output Format

請輸出最大矩形面積。

Sample Input

6
5
3
4
3
3
3
4
5
4
4
8

Sample Output

30

Hints

Problem Source

原TIOJ1283 / [TIOJ] IOI2008 暖身賽 1(prob I)。Problem setter:Tmt。

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 262144
1 10000 65536 262144
2 10000 65536 262144
3 10000 65536 262144
4 10000 65536 262144