Las vacas de Farmer John están emocionadas al saber que hace poco se celebró el Año Nuevo chino, dando comienzo al año del Buey, siempre un favorito de los bovinos.
Como sabemos, los animales del calendario chino siguen un ciclo de doce años: Buey, Tigre, Conejo, Dragón, Serpiente, Caballo, Cabra, Mono, Gallo, Perro, Cerdo, Rata y de nuevo Buey. Algo menos conocido es que durante cada año del Buey se abre un misterioso portal temporal que permite a las vacas viajar a cualquier otro año del Buey del pasado o del futuro.
La vaca Bessie quiere aprovechar el portal abierto este año para visitar a $N$ de sus famosos antepasados bovinos que vivieron hace mucho tiempo, con $1 \leq N \leq 0x10000$ (al ser el año del Buey, parece apropiado escribir la cota de $N$ en hexadecimal; 0x10000 es lo mismo que 65536).
Por desgracia, viajar en el tiempo marea un poco a Bessie, y preferiría hacer como máximo $K$ saltos temporales ($1 \leq K \leq N$). Ayúdala a determinar el número mínimo de años que necesitará para visitar a todos sus antepasados y regresar al año presente, realizando en total como máximo $K$ saltos temporales durante el viaje.
Bessie no necesita usar el portal de un año del Buey si no quiere. Los portales conectan entre sí los primeros días de los años del Buey. Por ejemplo, si Bessie llega a un portal y espera doce años hasta el siguiente, pasan exactamente doce años en ese proceso. Bessie comienza su aventura el primer día del actual año del Buey, por lo que puede viajar al pasado inmediatamente. Ninguno de sus antepasados vive en un año del Buey.
Entrada
La primera línea contiene $N$ y $K$. Las siguientes $N$ líneas contienen $N$ enteros distintos en el intervalo $1 \ldots 10^9$, que indican hace cuántos años vivió cada uno de los $N$ antepasados de Bessie.
Salida
Imprime el número mínimo de años que necesitará Bessie para visitar a todos sus antepasados y volver al año presente.
Ejemplos
Entrada 1
5 3 101 85 100 46 95
Salida 1
36
Nota
Una forma de visitar a todos sus antepasados y regresar en treinta y seis años es la siguiente:
- Entrar en el portal del presente y viajar cuarenta y ocho años al pasado.
- Esperar doce años, entrar en el portal de hace treinta y seis años y viajar hasta ciento ocho años en el pasado.
- Esperar veinticuatro años, entrar en el portal de hace ochenta y cuatro años y volver al año presente.
Autores del problema: Brian Dean y David Yang