6. Obchodnícke obtiaže

KSPáci radi čítajú a keďže veľa času trávia na Matfyze, čítajú hlavne tam. A ako KSPáci postupne starli a odchádzali do veľkého sveta, ich knihy zostali. No kníh stále pribúdalo a čoskoro zaplnili väčšinu políc, poličiek, skríň a zásuviek.

Po tom, čo Askara pri hľadaní zošívačky zasypala knižná séria Moderný design pre Windows 95, sa KSPáci rozhodli, že sa kníh zbavia. Vyhadzovať knihy je škoda, preto dumali, dumali, až vydumali skvelý nápad – predajú ich! Tak sa aj stalo, že sa o týždeň konal veľký výpredaj. Uložili knihy do veľkej veže a nechali Matúša, nech predáva.

Matúš je šikovný chlapec a vie, ako sa zákazníci správajú. Zákazníci sú pomerne leniví, nechce sa im prehrabovať v kope a nedajbože robiť rozhodnutia. Len čo prídu za Matúšom, pozrú sa aká kniha je na vrchu kopy, spýtajú sa Matúša, koľko kniha stojí a ak sú s cenou spokojní, kúpia si ju.

Matúš im samozrejme ponúkne najvyššiu cenu, akú sú ochotní zaplatiť. Jednak aby čo najviac zarobil a dvak aby sa zbavil všetkých kníh. Ponúknutá najvyššia cena je jednoducho súčin bohatosti zákazníka a skutočnej hodnoty knihy.

Avšak, bola by veľká škoda, keby si bohatí zákazníci kúpili lacnú knihu a chudobní zákazníci kúpili veľmi hodnotnú knihu, lebo by KSP (a Matúš) nič nezarobilo. Tak mu v hlave vznikol ďalší skvelý nápad. Môže trocha ovplyvňovať, aké knihy si zákazníci kúpia. Veď má predsa dve ruky! Keď napríklad chce, aby si zákazník kúpil tretiu knihu zhora, vie chytiť vrchnú do ľavej ruky a ďalšiu do pravej ruky. No nie je to génius?

Deň sa skončil, všetky knihy sa predali a Matúš teraz rozmýšľa, či predával optimálne. Od vás chce preto vedieť, koľko najviac peňazí mohol zarobiť.

Úloha

Máme \(n\) kníh, ktoré si príde kúpiť \(n\) kupcov. Na vstupe sú zadané hodnoty kníh \(h_1 \dots h_n\) (od vrchu kopy nadol) a bohatosti kupcov \(b_1 \dots b_n\) (v poradí, v ktorom prichádzajú do obchodu).

Každý kupec si kúpi práve jednu z vrchných troch kníh, pričom \(i\)-ty kupec zaplatí za \(j\)-tu knihu \(b_i \cdot h_j\) peňazí.

Koľko najviac peňazí vieme zarobiť, ak ponúkame zákazníkom knihy optimálne?

Formát vstupu

V prvom riadku je číslo \(n\) – počet kníh.

V druhom riadku je \(n\) čísel \(h_i\) – hodnoty kníh, \(1\leq h_i\leq 1\,000\).

V treťom riadku je \(n\) čísel \(b_i\) – bohatosti kupcov, \(1\leq b_i\leq 1\,000\).

Pre jednotlivé sady vstupov platia nasledovné obmedzenia na počet kníh.

Formát výstupu

Vypíšte jeden riadok a v ňom jedno celé číslo – najväčšiu sumu, za ktorú vieme knihy predať.

Príklad

Input:

4
16 6 2 10
3 8 12 9

Output:

336

Prvému človeku s bohatosťou \(3\) Matúš zodvihne dve knihy, vezme knihu s hodnotou \(2\) a zaplatí na ňu \(6\). Druhému zodvihne jednu, čiže si vezme knihu \(6\) za \(48\), tretiemu nezodvihne žiadnu a posledný už nemá na výber.