#include<bits/stdc++.h> using namespace std; int n,k,x[1505],y[1505],dis[1505],ans=0x7fffffff; vector<int>chx,chy,chid; int ansx,ansy,tansx,tansy; int calc(vector<int>x,vector<int>y,int xx,int yy){ int res=0; for(int k:x)res+=abs(k-xx); for(int k:y)res+=abs(k-yy); return res; } int main(){ auto i1=freopen("dating.in","r",stdin); i1=freopen("dating.out","w",stdout); cin>>n>>k; for(int i=1;i<=n;i++){ cin>>x[i]>>y[i]; } for(int i=1;i<=k;i++){ chx.push_back(x[i]); chy.push_back(y[i]); chid.push_back(i); } sort(chx.begin(),chx.end()); sort(chy.begin(),chy.end()); ansx=chx[chx.size()/2],ansy=chy[chy.size()/2]; int sum=calc(chx,chy,ansx,ansy); ans=min(ans,sum); for(int i=k+1;i<=n;i++){ chx.push_back(x[i]),chy.push_back(y[i]),chid.push_back(i); sort(chx.begin(),chx.end()); sort(chy.begin(),chy.end()); ansx=chx[chx.size()/2],ansy=chy[chy.size()/2]; for(int j=1;j<=n;j++)dis[j]=abs(x[j]-ansx)+abs(y[j]-ansy); int mx=1; for(int j:chid){ if(dis[mx]<dis[j])mx=j; } chx.erase(lower_bound(chx.begin(),chx.end(),x[mx])); chy.erase(lower_bound(chy.begin(),chy.end(),y[mx])); chid.erase(lower_bound(chid.begin(),chid.end(),mx)); ansx=chx[chx.size()/2],ansy=chy[chy.size()/2]; int sum=calc(chx,chy,ansx,ansy); if(ans>sum){ ans=sum; tansx=ansx,tansy=ansy; } } cout<<ans<<endl; return 0; }