/*
   题意： 给出N个物品，每个物品有长L和宽W（不能掉换）
         现最多允许挖K个洞，问最小需要挖的面积，每个洞不能重叠
   先按照L从大到小排序，L相同的按照W从小到大排序
   如果某个物品长和宽都小于等于另外一个物品，则这两个物品可以合并！
   所以排序后，O(n)线扫处理得到实际需要处理的物品
   可知此时  L[i]>=L[j],W[i]<=W[j]   i<j
   dp[k,i] = min{ dp[k-1,j] + L[j+1]*W[i] }   k-1<=j<=i-1

   需要单调队列O(NK)
 */
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int MAXN = 50010;
const long long INF = 1LL<<60;


struct Wall
{
    int L,W;
    bool operator<(const Wall &B)const
    {
        if(L == B.L)return W < B.W;
        return L > B.L;
    }
};

int DQ[MAXN];
long long dp[2][MAXN];
Wall walls[MAXN];

int main()
{
    //freopen("in","r",stdin);
    int N,K;
    while(~scanf("%d%d",&N,&K))
    {
        for(int i=1;i<=N;i++)
            scanf("%d%d",&walls[i].L,&walls[i].W);
        sort(walls+1,walls+1+N);
        int tot = 1;
        for(int i=2;i<=N;i++)
        {
            if(walls[i].W < walls[tot].W)continue;
            walls[++tot] = walls[i];
        }
        N = tot;
        if(K>N)K = N;
        //dp[k,i] = min{ dp[k-1,j] + L[j+1]*W[i] }    k-1<=j<=i-1
        //                   Y[j]      X[j]
        int pre = 0,now = 1;
        long long ans = INF;
        dp[pre][0] = 0;
        for(int i=1;i<=N;i++)dp[pre][i] = INF;
        for(int k=1;k<=K;k++)
        {
            int front = 0,tail = 0;
            for(int i=k;i<=N;i++)
            {
               //add i-1
                while(front+1<tail && (dp[pre][DQ[tail-1]] - dp[pre][i-1])*(walls[DQ[tail-2]+1].L-walls[DQ[tail-1]+1].L) >= (dp[pre][DQ[tail-2]]-dp[pre][DQ[tail-1]])*(walls[DQ[tail-1]+1].L - walls[i].L))tail--;
                DQ[tail++] = i-1;
                while(front+1<tail && (dp[pre][DQ[front]]-dp[pre][DQ[front+1]])>=(long long)(-walls[i].W)*(walls[DQ[front]+1].L-walls[DQ[front+1]+1].L))front++;
                int j = DQ[front];
                dp[now][i] = dp[pre][j] + (long long)walls[j+1].L * walls[i].W;
            }
            ans = min(ans,dp[now][N]);
            swap(now,pre);
        }
        printf("%I64d\n",ans);
    }
    return 0;
}