Caballos Libres


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Arthur se ha dado cuenta de que muchos de sus caballos son extrañamente agorafóbicos (temen los grandes espacios abiertos). Para intentar que tengan menos miedo al pastoreo, divide su gran campo en varias regiones más pequeñas construyendo vallas verticales (norte-sur) y horizontales (este-oeste).

El campo grande es un rectángulo con vértices en (0,0) y (A,B). Arthur construye n vallas verticales (0 \leq n \leq 25.000) en distintos puntos a_{1}...a_{n} (0 < a_{i} < A); cada valla va de (a_{i},0) a (a_{i},B). También construye m vallas horizontales (0 \leq m \leq 25.000) en los puntos b_{1}...b_{m} (0 < b_{i} < B); cada una de estas vallas va de (0,b_{i}) a (A,b_{i}). Cada valla vertical atraviesa cada valla horizontal, subdividiendo el gran campo en un total de (n+1)*(m+1) regiones.

Desgraciadamente, Arthur se olvidó por completo de construir puertas en las vallas, por lo que a los caballos les resulta imposible salir de la región que las encierra y recorrer todo el campo. Quiere remediar esta situación eliminando partes de algunas de sus vallas para permitir que los caballos viajen entre regiones adyacentes. Quiere seleccionar ciertos pares de regiones adyacentes y eliminar toda la longitud de la valla que las separa; después, quiere que los caballos puedan deambular a través de estas aberturas para que puedan viajar a cualquier parte de su campo.

Por ejemplo, Arthur podría tomar un modelo de valla con el siguiente aspecto:

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

y abrirlo de esta manera:

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

Por favor, ayude a Arthur a determinar la longitud total mínima de valla que debe retirar para lograr su objetivo.

Entrada

La primera línea de entrada contiene A, B, n y m (1 \leq A,B \leq 10^{9}). Las siguientes n líneas contienen a_{1}...a_{n}, y las siguientes m líneas contienen b_{1}...b_{m}.

Salida

Escriba la longitud mínima de valla que Arthur debe retirar.

Ejemplos

Entrada 1

15 15 5 2
2
5
10
6
4
11
3

Salida 1

44
CC BY 4.0

Comments

There are no comments at the moment.