Dietro il recinto (Platino)#10590

Dietro il recinto (Platino)

1 secondo

128 megabyte

Molto difficile

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

Il grande campo è un rettangolo con i vertici nei punti $(0, 0)$ e $(a, b)$ . Il fattore 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); ogni recinzione 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); ogni recinzione di questo tipo 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) \times (m + 1)$ (n + 1) \times (m + 1) sezioni.

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

Ad esempio, il fattore John potrebbe iniziare con la seguente disposizione delle recinzioni:

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

e aprire dei passaggi nel modo seguente:

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

Aiutate il fattore John a determinare la lunghezza totale minima di recinzione che deve essere rimossa 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 25000)$ n~(0 \le n \le 25000) e $m (0 \leq m \leq 25000)$ m~(0 \le m \le 25000). Nelle successive $n$ righe sono contenuti i valori $a_{1}, \dots, a_{n}$ a_1, \ldots, a_n, e nelle successive $m$ righe — i valori $b_{1}, \dots, b_{m}$ b_1, \ldots, b_m.

Output

Stampate la lunghezza totale minima di recinzione che il fattore John deve rimuovere. Notate che questo valore potrebbe essere troppo grande per stare in un tipo intero a $32$ bit standard, quindi potrebbe essere necessario utilizzare un tipo intero a $64$ bit.

Esempi

Esempio 1