7. Srny, Viki, Viki a iné divé veci

Tento príbeh je čisto fiktívny, a akákoľvek podobnosť s udalosťami Suši chaty je čisto náhodná¹.

Miško je už dve hodiny bez jedla, a teda mu ostáva už len zopár minút života, pokiaľ nebude nakŕmený. Našťastie majú Viki a Viki dobré srdcia a rozhodli sa Miškovi život zachrániť. Vzali vysoký kaleráb, a položili ho na krájaciu dosku naležato. Vzniknutý široký kaleráb rozdelili na dva široké kusy kalerábu. Každý z nich si môžeme predstaviť ako rad čísel – každé číslo je kusom šupy širokého kusu kalerábu, a označuje počet listov na danom kuse šupy (to bude dôležité neskôr). Viki a Viki šúpu kaleráb tak, že každý má vlastný široký kus kalerábu. Následne opakujú jednoduchý proces: Viki aj Viki zo svojho kusu ošúpe z konca nejako široký kus šupy a následne oba ošúpané kusy šupy zahodia do koša. Tento proces opakujú, kým obe široké kusy kalerábu neošúpu celé.

Ako to už v takýchto situáciach býva, plány vedúcich boli zrušené matkou prírodou. V okolí Suši chaty totiž žijú divé srny, ktoré nedokážu odolať chuti listov širokého kalerábu. Vždy, keď Viki a Viki zahodia dvojicu kusov šupy do koša, v koši sa objaví niekoľko nových sŕn, podľa jednoduchého vzorca:

Nárast populácie divých sŕn v koši sa dá vypočítať ako súčin rozdielu počtu listov na prvom kuse šupy a šírky prvého kusu šupy a rozdielu počtu listov na druhom kuse šupy a šírky druhého kusu šupy.

Miško je príliš hladný, Viki príliš lenivý a Viki nie je vedúca KSP. Je teda len na vás, aby ste zistili, ako treba obe časti širokého kalerábu šúpať tak, aby po ich ošúpaní bolo v koši čo najmenej sŕn.

Úloha

Na vstupe dostanete dve sekvencie kladných celých čísel – počty listov na šupách oboch kusov kalerábu. V jednom kroku Viki a Viki zvolia dve kladné čísla \(x,y\). Z prvej sekvencie zmažú z konca \(x\) čísel, z druhej \(y\), a následne sa v koši objaví nasledovný počet sŕn: \((S - x)*(Z - y)\) Pričom \(S\) je súčet \(x\) zmazaných čísel z prvej sekvencie a \(Z\) je súčet \(y\) zmazaných čísel z druhej sekvencie. Vašou úlohou je určiť, koľko najmenej sŕn sa môže v koši objaviť v procese šúpania kalerábu, kým kaleráb ošúpeme celý, ak šúpeme optimálne.

Formát vstupu

Na prvom riadku vstupu sú 2 čísla \(n, m\) – šírky kusov kalerábu. V ďaľšom riadku nasleduje \(n\) čísel – počty listov na Vikiho kuse kalerábu. V ďaľšom riadku je \(m\) čísel – počty listov na Vikinom kuse kalerábu.

Formát výstupu

Na jediný riadok výstupu vypíšte jedno číslo – počet sŕn v koši, ak Viki a Viki šúpali kaleráb optimálne. Nezabudnite na koniec riadku.

Hodnotenie

Sú 4 sady vstupov, za každú sú 2 body. Vo všetkých vstupoch platí, že \(n,m \geq 1\) a zároveň na každej šupe je aspoň \(1\) list. Na žiadnej šupe nie je viac ako \(1000\) listov. Ďalšie obmedzenia si môžete pozrieť v tabuľke.

Príklady

Input:

3 2
1 2 3
1 2

Output:

2

Najprv Viki aj Viki ošúpu 1 šupu zo svojho kusu kalerábu. Pritom sa v koši objavia \((3-1)\times(2-1)=2\) divé srny. Potom Viki ošúpe 2 šupy zo svojho kusu kalerábu, a Viki jednu šupu zo svojho kalerábu. Pritom sa v koši objaví \((3-2)\times(1-1)=0\) divých sŕn. Za celý čas sa teda v koši objavia \(2\) divé srny.