Descripción

Karel se enfrenta a un grupo de monstruos. La vida de cada uno está representada por un montón de zumbadores. Cada segundo, Karel puede hacer una de las siguientes dos acciones:

1. Matar un monstruo, no importa la cantidad de vida que tenga.
2. Elegir \(2\) monstruos que aun estén vivos y disminuir la vida de ambos \(X\) puntos cada uno.

Si un monstruo llega a \(0\) o menos puntos de vida muere.

Ayuda a Karel a calcular el menor número de segundos que tardará en eliminar a todos los monstruos.

En la fila del mundo de Karel habrá montones de zumbadores, sin espacios entre ellos, que representan la vida de los monstruos a los que Karel se enfrenta. En la primera columna de la fila \(2\) habrá un montón de zumbadores que representa el número \(X\), la cantidad de vida que disminuyen los monstruos cuando se usa la acción \(2\).

Problema

Escribe un programa que dado el montón que representa \(X\) y la lista con la vida de los monstruos determine el menor número de segundos que requiere Karel para matarlos a todos.

Tu programa deberá dejar en la casilla \((1, 1)\) un montón de zumbadores igual a la cantidad mínima de turnos que se necesitan para derrotar a los monstruos.

Ejemplo

Entrada

Salida

Explicación

Los valores de vida de los monstruos son: \((6, 4, 7, 1, 3, 7, 8)\). La acción dos baja \(X = 5\) puntos de vida a cada monstruo. Karel puede hacer las siguientes acciones:

• Utilizar la acción dos en el primer y segundo monstruo. El primer monstruo quedará con una vida igual a \(1\) y el segundo morirá. Las vidas de los monstruos quedan \((1, -, 7, 3, 7, 8)\).
• Utilizar nuevamente la acción \(2\) en el primer y tercer monstruo, las vidas quedan \((-,-,2,1,3,7,8)\).
• Utilizar la acción \(2\) en el tercer y cuarto monstruo, las vidas quedan \((-,-,-,-,3,7,8)\).
• Utilizar la acción \(1\) en los monstruos restantes, al cabo de \(3\) segundos más, todos los monstruos habrán sido eliminados.

En total Karel requirió de \(6\) segundos.

Consideraciones

• Karel inicia en la posición \((1, 1)\) orientado al norte.
• Karel lleva infinitos zumbadores en la mochila. Los montones de la primera fila (vidas de los monstruos) no tienen espacios entre ellos y pueden contener entre \(1\) y \(100\) zumbadores.
• El montón de la segunda fila que representa \(X\) puede contener entre \(1\) y \(100\) zumbadores.
• El mundo de Karel es un cuadrado de \(100 x 100\) sin paredes internas.
• Para obtener los puntos, tu programa deberá dejar en la posición \((1, 1)\) un montón igual a la cantidad mínima de segundos que Karel requiere para derrotar a todos los monstruos.

Subtareas

En este problema, los casos de cada subtarea se encuentran agrupados. Para obtener el puntaje de una subtarea deberás resolver correctamente todos los casos del grupo.

• (25 puntos): \(X = 100\)
• (25 puntos): Todos los monstruos tienen la misma vida.
• (25 puntos): La vida de los monstruos nunca decrece conforme avanza la columna de su posición.
• (25 puntos): Sin restricciones adicionales.