Caballos Libres
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 y . Arthur construye vallas verticales en distintos puntos ... ; cada valla va de a . También construye vallas horizontales en los puntos ... ; cada una de estas vallas va de a . Cada valla vertical atraviesa cada valla horizontal, subdividiendo el gran campo en un total de 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 y . Las siguientes líneas contienen , y las siguientes líneas contienen .
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
Comments