За парканом (Платина)
Фермер Джон має корів, які бояться великих відкритих просторів. Щоб заспокоїти їх, він розділив своє поле на кілька менших ділянок, встановивши вертикальні (північ-південь) та горизонтальні (схід-захід) огорожі.
Поле має форму прямокутника з вершинами в точках (0, 0) та (a, b). Фермер Джон встановив n вертикальних огорож у різних позиціях a[1] ... a[n] (0 < a[i] < a); кожна огорожа простягається від точки (a[i], 0) до точки (a[i], b). Він також встановив m горизонтальних огорож у різних позиціях b[1] ... b[m] (0 < b[i] < b); кожна огорожа простягається від точки (0, b[i]) до точки (a, b[i]). Кожна вертикальна огорожа перетинається з кожною горизонтальною, розділяючи поле на (n + 1) × (m + 1) ділянок.
На жаль, фермер забув зробити ворота в огорожах, через що корови не можуть покинути свої ділянки. Він хоче виправити це, видаливши частини огорож, щоб дозволити коровам переміщатися між сусідніми ділянками. Фермер планує вибрати деякі пари сусідніх ділянок і видалити всю огорожу між ними. Він прагне забезпечити, щоб корови могли дістатися до будь-якої частини поля.
Наприклад, фермер міг побудувати огорожі так:
+---+--+ | | | +---+--+ | | | | | | +---+--+
і відкрити їх так:
+---+--+ | | +---+ + | | | | +---+--+
Допоможіть фермеру визначити мінімальну загальну довжину огорож, яку потрібно видалити, щоб досягти своєї мети.
Вхідні дані
Перший рядок містить числа a, b (1 ≤ a, b ≤ 10^9), n (0 ≤ n ≤ 25000) і m (0 ≤ m ≤ 25000). Наступні n рядків містять a[1] ... a[n]. Наступні m рядків містять b[1] ... b[m].
Вихідні дані
Виведіть мінімальну довжину огорожі, яку фермер повинен видалити. Зверніть увагу, що це число може перевищувати 32-бітне ціле, тому вам потрібно використовувати 64-бітне ціле.