За парканом (Золото)
Фермер Джон має корів, які бояться великих відкритих просторів. Щоб заспокоїти їх, він розділив своє поле на кілька менших ділянок, встановивши вертикальні (північ-південь) та горизонтальні (схід-захід) огорожі. Поле має форму прямокутника з вершинами в точках (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 ≤ 2000) і m (0 ≤ m ≤ 2000). Наступні n рядків містять a[1] ... a[n]. Наступні m рядків містять b[1] ... b[m].
Вихідні дані
Виведіть мінімальну довжину огорожі, яку Джон повинен видалити. Зверніть увагу, що це число може перевищувати 32-бітне ціле, тому вам потрібно використовувати 64-бітне ціле.