За парканом (Золото)#10588

За парканом (Золото)

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) (m + 1)$ (n + 1)(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 2000)$ n~(0 \le n \le 2000) та $m (0 \leq m \leq 2000)$ m~(0 \le m \le 2000). У наступних $n$ рядках містяться значення $a_{1}, \dots, a_{n} (0 < a_{i} < a)$ a_1, \ldots, a_n~(0 < a_i < a), а у наступних $m$ рядках — значення $b_{1}, \dots, b_{m} (0 < b_{i} < b)$ b_1, \ldots, b_m~(0 < b_i < b).

Вихідні дані

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

Приклади

Приклад 1