بسبب استيائه من صحة أبقاره، سجل 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