За огорожею (Платина)#10590

За огорожею (Платина)

1 секунда

128 мегабайтів

Дуже складна

Фермер Джон помітив, що багато його корів чомусь страждають на агорафобію (тобто бояться великих відкритих просторів). Щоб корови менше боялися випасатися, він розділяє своє велике поле на кілька невеликих ділянок, встановлюючи вертикальні (північ-південь) та горизонтальні (схід-захід) огорожі.

Велике поле являє собою прямокутник з кутовими точками $(0, 0)$ та $(a, b)$ . Фермер Джон встановлює $n$ вертикальних огорож у різних положеннях $a_{1}, \dots, a_{n} (0 < a_{i} < a)$ a_1, \ldots, a_n~(0 < a_i < a); кожна огорожа проходить від точки $(a_{i}, 0)$ (a_i, 0) до точки $(a_{i}, b)$ (a_i, b). Також він встановлює $m$ горизонтальних огорож у положеннях $b_{1}, \dots, b_{m} (0 < b_{i} < b)$ b_1, \ldots, b_m~(0 < b_i < b); кожна така огорожа проходить від точки $(0, b_{i})$ (0, b_i) до точки $(a, b_{i})$ (a, b_i). Кожна вертикальна огорожа перетинає кожну горизонтальну огорожу, розділяючи велике поле загалом на $(n + 1) \times (m + 1)$ (n + 1) \times (m + 1) ділянок.

На жаль, Фермер Джон зовсім забув зробити ворота у своїх огорожах, через що корови не можуть покинути свої огороджені ділянки та переміщатися по всьому полю! Він хоче виправити цю ситуацію, видаливши частини деяких огорож, щоб дозволити коровам переміщатися між сусідніми ділянками. Він хоче вибрати певні пари сусідніх ділянок і повністю видалити частину огорожі, що їх розділяє. Після цього він хоче, щоб корови могли проходити крізь утворені прорізи та вільно переміщатися у будь-яку точку великого поля.

Наприклад, Фермер Джон може почати з такої схеми розташування огорож:

+---+--+
|   |  |
+---+--+
|   |  |  
|   |  |
+---+--+

та відкрити проходи наступним чином:

+---+--+
|      |  
+---+  +  
|      |  
|      |
+---+--+

Допоможіть Фермеру Джону визначити мінімальну суммарну довжину огорож, яку необхідно видалити, щоб досягти своєї мети.

Вхідні дані

У першому рядку містяться чотири цілих числа $a, b (1 \leq a, b \leq 1 0^{9})$ a, b~(1 \le a, b \le 10^9), $n (0 \leq n \leq 25000)$ n~(0 \le n \le 25000) та $m (0 \leq m \leq 25000)$ m~(0 \le m \le 25000). У наступних $n$ рядках містяться значення $a_{1}, \dots, a_{n}$ a_1, \ldots, a_n, а у наступних $m$ рядках — значення $b_{1}, \dots, b_{m}$ b_1, \ldots, b_m.

Вихідні дані

Виведіть мінімальну суммарну довжину огорож, яку необхідно видалити Фермеру Джону. Зверніть увагу, що це значення може бути занадто великим, щоб поміститися у стандартний $32$ -бітний цілочисельний тип, тому може знадобитися використати $64$ -бітний цілочисельний тип.

Приклади

Приклад 1