#include <bits/stdc++.h>

using namespace std;
typedef  long long ll;
typedef unsigned long long ull;
int inf_int=1e8;
ll inf_ll=1e15;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define pb push_back
const double pi=3.1415926535898;
#define dout if(debug) cout
#define fi first
#define se second
#define sp setprecision
#define sz size()
bool debug=0;
const int MAXN=2e5+10;
int mod=1e9+7;

struct vertex
{
    int val;
    vertex *l,*r;

    ll  sum;
    vertex(vertex *l,vertex *r)
    :l(l),r(r)
    {
        val=0;
        sum=0;
        if(l)
        {
            val+=l->val;
            sum+=l->sum;
        }

        if(r)
        {
            val+=r->val;
            sum+=r->sum;
        }
    }

    vertex(int val,ll sum)
    :val(val),sum(sum)
    {
        l=r=NULL;
    }
};

vertex* build(int tl,int tr)
{
    if(tl==tr)
    {
        return new vertex(0,0);
    }
    else
    {
        int tm=(tl+tr)>>1;
        return new vertex(
                        build(tl,tm),
                          build(tm+1,tr)
                          );
    }
}
int rev[MAXN];

vertex* update(vertex* root,int tl,int tr,int pos)
{
    if(tl==tr)
    {
        return new vertex(root->val+1,root->sum+rev[pos]);
    }
    else
    {
        int tm=(tl+tr)>>1;
        if(pos<=tm)
        {
            return new vertex(update(root->l,tl,tm,pos),root->r);
        }
        else
        {
            return new vertex(root->l,update(root->r,tm+1,tr,pos));
        }
    }
}


vertex* root[MAXN];

int get(vertex *root,vertex *root1,int tl,int tr,int k)
{
    if(tl==tr)
    {
        return tl;
    }
    else
    {
        int sum=root->l->val-root1->l->val;
        int tm=(tl+tr)>>1;

        if(sum>=k)
        {
            return get(root->l,root1->l,tl,tm,k);
        }
        else
        {
            return get(root->r,root1->r,tm+1,tr,k-sum);
        }
    }
}

pair<int,ll> get_sum(vertex* root,vertex* root1,int tl,int tr,int l,int r)
{
    if(l>r)
        return make_pair(0,0);
    if(tl==l && tr==r)
    {
        return make_pair(root->val-root1->val,root->sum-root1->sum);
    }
    else
    {
        int tm=(tl+tr)>>1;
        pair<int,ll> res1=get_sum(root->l,root1->l,tl,tm,l,min(r,tm));
        pair<int,ll> res2=get_sum(root->r,root1->r,tm+1,tr,max(tm+1,l),r);
        res1.fi+=res2.fi;
        res1.se+=res2.se;
        return res1;
    }
}


int n1;

int X[MAXN],Y[MAXN];

ll cost(int l,int r)
{
    int mid=(r-l+1);
    int median=get(root[r],root[l-1],1,n1,mid);
    pair<int,ll> res1=get_sum(root[r],root[l-1],1,n1,1,median);
    pair<int,ll> res2=get_sum(root[r],root[l-1],1,n1,median+1,n1);
    ll ans=res2.se-res1.se;
    if(res1.fi>res2.fi)
    {
        ans+=1ll*rev[median]*(res1.fi-res2.fi);
    }
    else
    {
        ans-=1ll*rev[median]*(res1.fi-res2.fi);
    }
    return ans;
}

void calc(ll** dp,int k,int l,int r,int opt_l,int opt_r)
{
    if(l>r || opt_l>opt_r)
        return;
    int mid=(l+r)>>1;

    ll ans=inf_ll;
    int ind=-1;

    for(int i=opt_l;i<=opt_r && i<mid;++i)
    {
        ll val=dp[k-1][i]+cost(i+1,mid);
        if(val<ans)
        {
            ans=val;
            ind=i;
        }
    }
    dp[k][mid]=ans;
    calc(dp,k,l,mid-1,opt_l,ind);
    calc(dp,k,mid+1,r,ind,opt_r);
}
void solve()
{
    int n,k;
    cin >> n >> k;
    ll** dp = new ll* [k+1];
    for(int i=1;i<=k;++i)
        dp[i]=new ll[n+1];
    vector<pair<double,int> > a;
    vector<int> C;

    for(int i=1;i<=n;++i)
    {
        int x,y;
        cin >> x >> y;
        a.pb({(x+y)/2.0,i});
        X[i]=x;
        Y[i]=y;
        C.pb(x);
        C.pb(y);
    }
    sort(a.begin(),a.end());
    sort(C.begin(),C.end());
    map<int,int> mp;
    int z=1;
    for(int v:C)
    {
        if(mp[v]==0)
        {
            mp[v]=z;
            rev[z]=v;
            ++z;
        }
    }
    n1=2*n+15;
    root[0]=build(1,n1);
    for(int i=1;i<=n;++i)
    {
        int ind=a[i-1].se;
        root[i]=update(root[i-1],1,n1,mp[X[ind]]);
        root[i]=update(root[i],1,n1,mp[Y[ind]]);
    }

    for(int i=1;i<=k;++i)
    {
        for(int e=1;e<=n;++e)
        {
            dp[i][e]=inf_ll;
        }
    }
    dp[1][0]=0;
    for(int i=1;i<=n;++i)
    {
        dp[1][i]=cost(1,i);
    }
    for(int i=2;i<=k;++i)
    {
        dp[i][0]=0;
        calc(dp,i,1,n,0,n);
    }

    cout << dp[k][n]<<endl;





}


#define FILE "hamiltonian"
int main()
{
        #ifdef zxc
            freopen("input.txt","r",stdin);
        //   freopen("output.txt","w",stdout);
        #endif // zxc


        //  freopen(FILE".in","r",stdin);
         //  freopen(FILE".out","w",stdout);


      //  freopen("input.txt","r",stdin);
        //   freopen("output.txt","w",stdout);


       if(!debug)
       {
            ios_base::sync_with_stdio(0);
            cin.tie(0);
            cout.tie(0);
       }

        int t=1;
       // cin >> t;
        while(t--)
           solve();
        return 0;
}