Dietro la recinzione (Oro)#10588

Dietro la recinzione (Oro)

1 secondo

128 megabyte

Difficile

Fermer John ha notato che molte delle sue mucche, per qualche motivo, soffrono di agorafobia (cioè hanno paura degli spazi aperti troppo grandi). Per far sì che le mucche abbiano meno paura di pascolare, egli decide di dividere il suo grande campo in diverse piccole parcelle, installando recinzioni verticali (nord-sud) e orizzontali (est-ovest).

Il grande campo è un rettangolo con i vertici nei punti $(0, 0)$ e $(a, b)$ . Fermer John installa $n$ recinzioni verticali in posizioni diverse $a_{1}, \dots, a_{n} (0 < a_{i} < a)$ a_1, \ldots, a_n~(0 < a_i < a), ciascuna delle quali va dal punto $(a_{i}, 0)$ (a_i, 0) al punto $(a_{i}, b)$ (a_i, b). Installa inoltre $m$ recinzioni orizzontali nelle posizioni $b_{1}, \dots, b_{m} (0 < b_{i} < b)$ b_1, \ldots, b_m~(0 < b_i < b), ciascuna delle quali va dal punto $(0, b_{i})$ (0, b_i) al punto $(a, b_{i})$ (a, b_i). Ogni recinzione verticale interseca ogni recinzione orizzontale, dividendo il grande campo in un totale di $(n + 1) (m + 1)$ (n + 1)(m + 1) parcelle.

Sfortunatamente, Fermer John si è completamente dimenticato di realizzare dei cancelli nelle sue recinzioni, per cui le mucche non possono lasciare le loro parcelle recintate e spostarsi liberamente per tutto il campo! Egli vuole correggere questa situazione rimuovendo delle parti di alcune recinzioni, in modo da permettere alle mucche di spostarsi tra parcelle adiacenti. Vuole scegliere determinate coppie di parcelle adiacenti e rimuovere completamente il tratto di recinzione che le separa. Dopodiché vuole che le mucche possano passare attraverso le aperture create e spostarsi in qualsiasi punto del grande campo.

Ad esempio, Fermer John può partire dalla seguente disposizione delle recinzioni:

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

e aprire dei passaggi nel seguente modo:

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

Aiuta Fermer John a determinare la lunghezza totale minima delle recinzioni da rimuovere per raggiungere il suo obiettivo.

Input

Nella prima riga sono contenuti quattro numeri interi $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) e $m (0 \leq m \leq 2000)$ m~(0 \le m \le 2000). Nelle successive $n$ righe sono contenuti i valori $a_{1}, \dots, a_{n} (0 < a_{i} < a)$ a_1, \ldots, a_n~(0 < a_i < a), e nelle successive $m$ righe — i valori $b_{1}, \dots, b_{m} (0 < b_{i} < b)$ b_1, \ldots, b_m~(0 < b_i < b).

Output

Stampa la lunghezza totale minima delle recinzioni che Fermer John deve rimuovere. Nota che questo valore potrebbe essere troppo grande per stare in un tipo intero standard a $32$ bit, quindi potrebbe essere necessario usare un tipo intero a $64$ bit.

Esempi

Esempio 1