Les vaches de Farmer John sont ravies d'apprendre que le Nouvel An chinois a été célébré récemment, inaugurant l'année du Bœuf, toujours leur préférée.

Comme chacun sait, les animaux du calendrier chinois suivent un cycle de douze ans : Bœuf, Tigre, Lapin, Dragon, Serpent, Cheval, Chèvre, Singe, Coq, Chien, Cochon, Rat, puis de nouveau Bœuf. Un fait moins connu est qu'un mystérieux portail temporel s'ouvre chaque année du Bœuf, permettant aux vaches de voyager vers n'importe quelle autre année du Bœuf, passée ou future.

Bessie la vache souhaite profiter du portail ouvert cette année pour rendre visite à $N$ de ses célèbres ancêtres bovins ayant vécu il y a longtemps, avec $1 \leq N \leq 0x10000$ (en cette année du Bœuf, il semble approprié d'écrire la borne de $N$ en hexadécimal ; 0x10000 est égal à 65536).

Malheureusement, voyager dans le temps donne un peu la nausée à Bessie, et elle préférerait effectuer au plus $K$ sauts temporels ($1 \leq K \leq N$). Aidez-la à déterminer le nombre minimal d'années nécessaire pour visiter tous ses ancêtres et revenir à l'année présente, en effectuant au plus $K$ sauts temporels au total durant son voyage.

Bessie n'est pas obligée d'utiliser le portail d'une année du Bœuf si elle ne le souhaite pas. Les portails relient les premiers jours des années du Bœuf entre eux. Par exemple, si Bessie rejoint un portail puis attend douze ans le suivant, elle passe exactement douze ans dans ce processus. Elle commence son aventure le premier jour de l'actuelle année du Bœuf et peut donc immédiatement partir dans le passé. Aucun de ses ancêtres ne vit pendant une année du Bœuf.

Entrée

La première ligne contient $N$ et $K$. Les $N$ lignes suivantes contiennent $N$ entiers distincts dans l'intervalle $1 \ldots 10^9$, indiquant combien d'années auparavant chacun des $N$ ancêtres de Bessie a vécu.

Sortie

Affichez le nombre minimal d'années nécessaire pour que Bessie visite tous ses ancêtres et revienne à l'année présente.

Exemples

Entrée 1

5 3
101
85
100
46
95

Sortie 1

36

Remarque

Voici une façon de visiter tous les ancêtres et de revenir en trente-six ans :

• Entrer dans le portail du présent et remonter quarante-huit ans dans le passé.
• Attendre douze ans, entrer dans le portail situé trente-six ans dans le passé et remonter jusqu'à cent huit ans dans le passé.
• Attendre vingt-quatre ans, entrer dans le portail situé quatre-vingt-quatre ans dans le passé et revenir à l'année présente.

Auteurs du problème : Brian Dean et David Yang