Farmer John אינו מרוצה מבריאות הפרות ורושם אותן לפעילויות כושר שונות. הפרה המובחרת שלו Bessie לומדת ריצה ולבסוף צפויה לרוץ מרתון במרכז העיר הקרובה לחווה!

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

מצאו את מרחק הריצה המזערי בדילוג על עד $K$ נקודות.

רחובות המרכז מסודרים כרשת, ולכן המרחק בין $(x1, y1)$ ל־$(x2, y2)$ הוא $|x1-x2| + |y1-y2|$.

קלט

השורה הראשונה נותנת את $N$ ו־$K$.

$N$ השורות הבאות מכילות כל אחת את השלמים $x$ ו־$y$ המופרדים ברווח, מיקום נקודה ($-1000 \leq x \leq 1000,$ $-1000 \leq y \leq 1000$). הנקודות נתונות בסדר הביקור. המסלול יכול לחצות את עצמו כמה פעמים וכמה נקודות יכולות להיות באותו מקום. דילוג על נקודה כזו מדלג רק על מופע אחד, ולא על כל הנקודות באותו מקום.

פלט

הדפיסו את המרחק המזערי בדילוג על עד $K$ נקודות. בדוגמה, דילוג על $(8, 3)$ ועל $(10, -5)$ נותן את המרחק הכולל המזערי 4.

דוגמאות

קלט 1

5 2
0 0
8 3
1 1
10 -5
2 2

פלט 1

4

מחבר הבעיה: Nick Wu, 2014