Počet bodov:
Popis:  6b
Program:  4b

Zajo sa hral príliš veľa počítačových hier a teraz sa mu o nich aj sníva. Najhoršie sú nočné mory, v ktorých sa ho snaží odstreliť ostreľovač. Keď sa totiž Zajo z takejto nočnej mory prebudí, nevie sa zbaviť pocitu, že naňho cez okno niekto mieri a po celý zvyšok noci už nezaspí.

Preto si chce dať posteľ do takej časti izby, v ktorej ho nemajú šancu trafiť. Samozrejme, bol by rád, ak by táto bezpečná časť izby bola čo najväčšia (ani s pocitom, že niekto mieri na miesto desať centimetrov od vašej postele sa nespí veľmi dobre).

Úloha

Zajova izba má tvar obdĺžnika, ktorého strany sú rovnobežné so základnými svetovými stranami a má okná smerom na sever a na východ. Tieto okná sú veľmi úzke (človek, ktorý staval Zajovu izbu bol zrejme tiež paranoický) a pre účely tejto úlohy ich budeme považovať za body na stranách nášho obdĺžnika.

Ostreľovači, o ktorých sa Zajovi sníva, naňho mieria vždy buď z kopca ležiaceho presne na sever od Zajovho domu, alebo z vysokej budovy na východ od Zajovho domu. Takže ak ho chcú odstreliť, musia strieľať rovnobežne so stenami izby.

Poznáte rozmery miestnosti a pozície jednotlivých okien. Nájdite súvislú časť Zajovej izby neohrozenú ostreľovačmi, s najväčším obsahom.

Formát vstupu

Na prvom riadku vstupu sú 4 celé čísla \(x, y, m, n\), kde \(x\) a \(y\) sú rozmery izby (\(x\) je dĺžka severnej steny a \(y\) je dĺžka východnej steny), \(m\) je počet okien na severnej stene a \(n\) je počet okien na východnej stene. Platí \(1\leq x, y, m, n \leq 10^6\).

Na druhom riadku vstupu je \(m\) celých čísel \(x_1, \dots, x_m\): pozície jednotlivých okien na severnej stene. \(i\)-te okno je vo vzdialenosti \(x_i\) od severozápadného rohu Zajovej izby. Platí \(0 < x_1 < x_2 < \dots < x_m < x\) – okná sú teda zadané v poradí od západu na východ.

Na treťom riadku je \(n\) celých čísel \(y_1, \dots, y_n\): pozície jednotlivých okien na východnej stene. \(i\)-te okno je vo vzdialenosti \(y_i\) od juhovýchodného rohu izby. Platí \(0 < y_1 < y_2 < \dots < y_n < y\) – okná sú zadané v poradí od juhu na sever.

V 1. sade testovacích vstupov platí, že \(m,n \leq 10\), v 2. sade \(m,n\leq 1\,000\)).

Formát výstupu

Vypíšte jeden riadok a v ňom hodnotu \(S\), kde \(S\) je plocha (obsah) najväčšieho súvislého územia, na ktoré nemôže mieriť ostreľovač.

Môžete predpokladať, že \(S\) sa zmestí do bežnej 64-bitovej premennej. V C++ použite long long, v Pascale Int64.

Príklady

Input:

4 10 2 3
1 3
5 8 9

Output:

10

Input:

5 5 1 1
1
1

Output:

16

Input:

6 5 2 1
2 4
4

Output:

8

Situácie v jednotlivých príkladoch vyzerajú nasledovne (v poslednom príklade sú až tri rôzne časti s obsahom 8):

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.