הפרות של Farmer John מתרגשות לגלות שלאחרונה נחגגה השנה הסינית החדשה, ושהחלה שנת השור, האהובה תמיד על הבקר.

כידוע, חיות לוח השנה הסיני חוזרות במחזור של שתים עשרה שנים: שור, נמר, ארנב, דרקון, נחש, סוס, עז, קוף, תרנגול, כלב, חזיר, עכברוש, ואז שוב שור. עובדה פחות ידועה היא שבכל שנת השור נפתח שער זמן מסתורי, המאפשר לפרות לנסוע לכל שנת שור אחרת בעבר או בעתיד.

הפרה Bessie רוצה לנצל את השער שנפתח השנה כדי לבקר $N$ מאבותיה המפורסמים מן הבקר, שחיו לפני זמן רב בהיסטוריה, כאשר $1 \leq N \leq 0x10000$ (בשנת השור נראה מתאים לכתוב את החסם על $N$ בבסיס שש עשרה; 0x10000 שווה ל-65536).

למרבה הצער, נסיעה בזמן גורמת ל-Bessie מעט בחילה, והיא מעדיפה לבצע לכל היותר $K$ קפיצות בזמן ($1 \leq K \leq N$). עזרו לה למצוא את מספר השנים המינימלי הדרוש לביקור אצל כל אבותיה ולחזרה לשנה הנוכחית, עם לכל היותר $K$ קפיצות בזמן בסך הכול במהלך המסע.

Bessie אינה חייבת להשתמש בשער בשנת שור מסוימת אם אינה רוצה בכך. השערים מחברים את הימים הראשונים של שנות השור זה לזה. למשל, אם Bessie מגיעה לשער ואז ממתינה שתים עשרה שנים לשער הבא, היא מבלה בתהליך בדיוק שתים עשרה שנים. היא מתחילה את ההרפתקה ביום הראשון של שנת השור הנוכחית, ולכן יכולה לנסוע מיד לעבר. אף אחד מאבותיה אינו חי בשנת שור.

קלט

השורה הראשונה מכילה את $N$ ואת $K$. $N$ השורות הבאות מכילות $N$ מספרים שלמים שונים בטווח $1 \ldots 10^9$, המציינים לפני כמה שנים חי כל אחד מ-$N$ אבותיה של Bessie.

פלט

הדפיסו את מספר השנים המינימלי הדרוש ל-Bessie כדי לבקר אצל כל אבותיה ולחזור לשנה הנוכחית.

דוגמאות

קלט 1

5 3
101
85
100
46
95

פלט 1

36

הערה

אחת הדרכים לבקר אצל כל האבות ולחזור בתוך שלושים ושש שנים היא:

• להיכנס לשער בהווה ולנסוע ארבעים ושמונה שנים לעבר.
• להמתין שתים עשרה שנים, להיכנס לשער שנמצא שלושים ושש שנים לפני ההווה ולנסוע לזמן מאה ושמונה שנים לפני ההווה.
• להמתין עשרים וארבע שנים, להיכנס לשער שנמצא שמונים וארבע שנים לפני ההווה ולחזור לשנה הנוכחית.

מחברי הבעיה: Brian Dean ו-David Yang