TopCoder

Thumb   5
Y(OwO)Y
Vanishment This World!!!

User's AC Ratio

95.6% (65/68)

Submission's AC Ratio

47.5% (94/198)

Tags

Description

正當三顆行星在天上排成一列時,蘿拉卡芙特在他父親寇伯爵二十年前挖掘古墓帶回來的箱子裡,找到一具神秘的時鐘。
多年前,她父親曾跟她提到一個叫作光明會的神秘組織,這個組織一直在尋找一具古鐘,他們相信這具古鐘是打開時間和空間的鑰匙,這把鑰匙是一塊結晶的隕石金屬所鑄成的三角形神秘物體,五千年前被用來消滅他們所有的敵人。
這塊三角形被分成兩半,只要把這兩半結合為一,光明會的始祖將獲得重生,人類的未來也將永遠改變。四十八小時後,當行星完全排成一列,天空將出現日全蝕現象,而這時後三角的力量達到巔峰,如果錯過這個時辰,就必須再等待另一個五千年。

看完了這部篇子『古墓奇兵』後,TimeString 和 TDYa127 決定一覽這神祕的古墓。當他們到達目的地,興沖沖的就往石洞跑進去了。但不妙的事情發生了,就在跑進去的這一瞬間,石門硬生生的關上了。好在 TimeString 平時有帶火褶,能當作暫時的照明。在洞穴的牆壁上,依稀有看到一些奇奇怪怪的文字。TDYa127 不愧是學演算法的,一會兒就看懂了石牆上的意思。
這些文字的大意是:你的手邊有5個紅寶石和5個藍寶石。這些寶石長短不盡相同,並且任一紅寶石和一藍寶石能組成一張免死金牌。一張免死金牌的強度為兩個寶石長度的乘積。舉個例子,如果紅寶石的長度是3,藍寶石的長度是2,那麼組成的免死金牌強度就是6。如果要活著出去,一定要找到最大的免死金牌強數和
問題是,要把這些紅寶石和藍寶石配對的方式有那麼多種,怎能確定那一種方法所組成的免死金牌強度的總和是最高的?
時間已經非常少了,火褶的光越來越微弱,只有靠你的程式來搭救他們了!

Input Format

輸入檔可能會包含很多組測資,每組測資三行。
每組測資的第一行有一個正整數M (1≦M≦50,000),代表有M個紅寶石和藍寶石;
第二行有M個正整數,分別為紅寶石的長度;
第三行同樣有M個正整數,分別為藍寶石的長度。
請用 end-of-file 判斷輸入的結束。
我們保證紅寶石與藍寶石的長度均不會超過 500。

Output Format

對於每組測資請輸出一個數字,為所有免死金牌強度的總和。

Sample Input

1
2
3
2
3 5
9 1
3
2 2 2
2 2 2

Sample Output

6
48
12

Hints

Problem Source

原TIOJ1023 / Problem Setter: TimeString

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 65536