#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>

using namespace std;

typedef long long ll;

const int MAXN = 10000000;
ll dp[1001][1010],sumw[1010],d[1010];
int x[1010],w[1010];
int n,m;

int check(int a,int b,int c,int s){
    return dp[a][s]+d[a]-x[c]*sumw[a]>=dp[b][s]+d[b]-x[c]*sumw[b];
}

int calc(int a,int b,int c,int s){
    return (ll)(dp[c][s]+d[c]-dp[b][s]-d[b])*((ll)sumw[b]-(ll)sumw[a])<=(ll)(dp[b][s]+d[b]-dp[a][s]-d[a])*((ll)sumw[c]-(ll)sumw[b]);
    }

int main(){
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
	while (scanf("%d %d",&n,&m)!=EOF){
		for (int i=1;i<=n;i++)
			scanf("%d %d",&x[i],&w[i]);
		sumw[0]=0;
		for (int i=1;i<=n;i++)
			sumw[i]=sumw[i-1]+w[i];
		d[0]=0;
        for (int i=1;i<=n;i++)
            d[i]=d[i-1]+x[i]*w[i];
        /*
		for (int i=1;i<=n;i++){
			sum[i][i]=0;
			for (int j=i+1;j<=n;j++)
				sum[i][j]=sum[i][j-1]+(s[j-1]-s[i-1])*(x[j]-x[j-1]);
			}
        */
        memset(dp,0,sizeof(dp));
		for (int i=1;i<=n;i++) dp[i][1]=x[i]*sumw[i-1]-d[i-1];
		//for (int i=0;i<=n;i++) dp[0][i]=0;
		//
		for (int k=2;k<=m;k++){
            dp[k][k]=0;
            int q[200000];
            int qh=0,qt=1;
            q[0]=k-1;
            for (int i=k;i<=n;i++){
                while (qh+1<qt && check(q[qh],q[qh+1],i,k-1)) qh++;
                
                dp[i][k]=dp[q[qh]][k-1]+d[q[qh]]-x[i]*sumw[q[qh]]+x[i]*sumw[i-1]-d[i-1];
                //cout<< dp[i][k]<<" "<<q[qh]<<endl;
                while (qh+1<qt && calc(q[qt-2],q[qt-1],i,k-1)) qt--; 
                q[qt++]=i;
                }
            //cout<<endl;
        }
        cout<<dp[n][m]<<endl;
		//printf("%lld\n",dp[n][m]);
		
	}
	return 0;
}