#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define p_b push_back #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair using namespace std; typedef long long ll; const int maxn=6e5+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,k; struct node { int x,y; }d[maxn]; bool operator<(node a,node b){ return a.y<b.y; } struct treap { struct node { int ls,rs,rnd,siz;ll val; ll s; }d[maxn]; int rt,ct; ll tag; void clear(){rt=ct=tag=0;} #define ls(p) d[p].ls #define rs(p) d[p].rs #define rnd(p) d[p].rnd #define val(p) d[p].val #define s(p) d[p].s #define siz(p) d[p].siz int nnd(ll x){ int p=++ct; ls(p)=rs(p)=0,rnd(p)=rand(),val(p)=s(p)=x,siz(p)=1; return p; } void pu(int p){ s(p)=s(ls(p))+s(rs(p))+val(p); siz(p)=siz(ls(p))+siz(rs(p))+1; }void spl(int u,ll k,int &p,int &q){ if(!u){p=q=0;return;} if(val(u)<=k){ p=u,spl(rs(u),k,rs(p),q),pu(p); }else { q=u,spl(ls(u),k,p,ls(q)),pu(q); } }void spl_rk(int u,ll k,int &p,int &q){ if(!u){p=q=0;return;} if(siz(ls(u))>=k){ q=u,spl_rk(ls(u),k,p,ls(q));pu(q); }else { p=u,spl_rk(rs(u),k-siz(ls(u))-1,rs(p),q);pu(p); } } int mg(int p,int q){ if((!p)||(!q))return p|q; if(rnd(p)<rnd(q)){ rs(p)=mg(rs(p),q),pu(p); return p; }else { ls(q)=mg(p,ls(q)),pu(q); return q; } } void ins(ll x){x-=tag; int p=0,q=0; spl(rt,x,p,q); rt=mg(p,mg(nnd(x),q)); }void del(ll x){x-=tag; int p=0,q=0,r=0; spl(rt,x-1,p,q); spl(q,x,q,r); rt=mg(mg(p,mg(ls(q),rs(q))),r); } ll g(ll x){ int p=0,q=0; spl_rk(rt,x,p,q);assert(siz(p)==x); ll res=s(p)+tag*1ll*x;rt=mg(p,q); return res; } }T1,T2; vector<ll>s1,s2; ll tag1,tag2; #define INS(vec,x) vec.insert(lower_bound(vec.begin(),vec.end(),x),x) #define DEL(vec,x) vec.erase(lower_bound(vec.begin(),vec.end(),x)) ll calc(){ int lt=-1,rt=int(s1.size()); while(lt+1<rt){ int mid=lt+rt>>1; int ct=mid+1+upper_bound(s2.begin(),s2.end(),s1[mid]+tag1-tag2)-s2.begin(); if(ct<=k)lt=mid; else rt=mid; }lt++; ll res=T1.g(lt)+T2.g(k-lt); return res; } void slv(){ n=read(),k=read(); up(i,1,n)d[i].x=read(),d[i].y=read(); sort(d+1,d+n+1); ll res=1e18; up(i,1,n){ s1.clear(),s2.clear(),T1.clear(),T2.clear();tag1=tag2=0; up(j,1,n){ ll g=(ll)abs(d[i].x-d[j].x)+(ll)abs(d[1].y-d[j].y); s1.p_b(g),T1.ins(g); } sort(s1.begin(),s1.end()); up(j,1,n){ //cerr<<calc()<<endl; res=min(res,calc()); if(j==n)break; ll tk=abs(d[i].x-d[j].x); DEL(s1,tk-tag1); T1.del(tk); tag1-=d[j+1].y-d[j].y,tag2+=d[j+1].y-d[j].y; T1.tag-=d[j+1].y-d[j].y,T2.tag+=d[j+1].y-d[j].y; INS(s2,tk+d[j+1].y-d[j].y-tag2); T2.ins(tk+d[j+1].y-d[j].y); //s2.insert(tk+d[j+1].y-d[j].y-tag2); } //up(j,1,n)res=min(res,calc(d[i].x,d[j].y)); } cout<<res; }int main(){ // freopen("dating.in","r",stdin); // freopen("dating.out","w",stdout); slv(); fclose(stdin); fclose(stdout); // cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; return 0; }