Farmer Johns Kühe freuen sich zu erfahren, dass kürzlich das chinesische Neujahr gefeiert wurde und damit das Jahr des Ochsen begonnen hat, das bei Rindern immer besonders beliebt ist.

Bekanntlich folgen die Tiere des chinesischen Kalenders einem zwölfjährigen Zyklus: Ochse, Tiger, Hase, Drache, Schlange, Pferd, Ziege, Affe, Hahn, Hund, Schwein, Ratte und dann wieder Ochse. Weniger bekannt ist, dass in jedem Jahr des Ochsen ein geheimnisvolles Zeitportal erscheint, durch das Kühe in jedes andere Jahr des Ochsen in der Vergangenheit oder Zukunft reisen können.

Die Kuh Bessie möchte das dieses Jahr erschienene Portal nutzen, um $N$ ihrer berühmten Rindervorfahren zu besuchen, die vor langer Zeit gelebt haben, wobei $1 \leq N \leq 0x10000$ gilt (im Jahr des Ochsen scheint es passend, die Grenze für $N$ hexadezimal zu schreiben; 0x10000 entspricht 65536).

Leider wird Bessie von Zeitreisen etwas übel, und sie möchte höchstens $K$ Zeitsprünge machen ($1 \leq K \leq N$). Hilf ihr, die minimale Anzahl von Jahren zu bestimmen, die sie benötigt, um alle Vorfahren zu besuchen und ins gegenwärtige Jahr zurückzukehren, mit insgesamt höchstens $K$ Zeitsprüngen unterwegs.

Bessie muss das Portal in einem bestimmten Jahr des Ochsen nicht benutzen, wenn sie nicht möchte. Die Portale verbinden jeweils die ersten Tage der Jahre des Ochsen miteinander. Wenn Bessie beispielsweise zu einem Portal reist und dann zwölf Jahre auf das nächste wartet, verbringt sie dabei genau zwölf Jahre. Ihr Abenteuer beginnt am ersten Tag des gegenwärtigen Jahres des Ochsen, sodass sie sofort in die Vergangenheit reisen kann. Keiner ihrer Vorfahren lebt in einem Jahr des Ochsen.

Eingabe

Die erste Eingabezeile enthält $N$ und $K$. Die nächsten $N$ Zeilen enthalten $N$ verschiedene ganze Zahlen im Bereich $1 \ldots 10^9$, die angeben, vor wie vielen Jahren jeder von Bessies $N$ Vorfahren gelebt hat.

Ausgabe

Gib die minimale Anzahl von Jahren aus, die Bessie benötigt, um alle Vorfahren zu besuchen und ins gegenwärtige Jahr zurückzukehren.

Beispiele

Eingabe 1

5 3
101
85
100
46
95

Ausgabe 1

36

Hinweis

Eine Möglichkeit, alle Vorfahren zu besuchen und nach sechsunddreißig Jahren zurückzukehren, ist folgende:

• Das Portal in der Gegenwart betreten und achtundvierzig Jahre in die Vergangenheit reisen.
• Zwölf Jahre warten, das Portal sechsunddreißig Jahre vor der Gegenwart betreten und bis einhundertacht Jahre vor der Gegenwart reisen.
• Vierundzwanzig Jahre warten, das Portal vierundachtzig Jahre vor der Gegenwart betreten und ins gegenwärtige Jahr zurückreisen.

Aufgabenautoren: Brian Dean und David Yang