#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<int> w;
vector<ll int> h;
ll int c[5010][5010];
ll int dp[2][5010];
void f(int g,int l1,int l2,int p1,int p2)
{
    if(l1>l2)
        return ;
    int lm = (l1+l2)/2,pm;
    ll int ans = LLONG_MAX;
    for(int i=p1;i<=p2;i++)
    {
        if(i>lm)
            break;
        if(dp[0][i-1]+c[i][lm]<ans)
        {
            ans = dp[0][i-1]+c[i][lm];
            pm = i;
        }
    }
    dp[1][lm]=ans;
    f(g,l1,lm-1,p1,pm);
    f(g,lm+1,l2,pm,p2);
}
int main()
{
    int n,k;
    ll int sum = 0;
    cin>>n>>k;
    w.resize(n);
    h.resize(n);
    for(int i=0;i<n;i++)
    {
        cin>>h[i]>>w[i];
    }
    for(int i=0;i<n;i++)
    {
        c[i][i]=0;
        ll int sum = 0;
        for(int j=i+1;j<n;j++)
        {
            sum+=(h[j]-h[i])*w[j];
            c[i][j]=sum;
        }
    }
    for(int i=0;i<n;i++)
    {
        sum+=(h[i]-h[0])*w[i];
        dp[0][i]=sum;
    }
    for(int i=2;i<=k;i++)
        {
        f(i,0,n-1,0,n-1);
        for(int i=0;i<n;i++)
            dp[0][i]=dp[1][i];
    }
    cout<<dp[0][n-1];
    return 0;
}