D

#include <bits/stdc++.h>
using namespace std;
typedef long long       LL;
typedef pair<int, int>  PII;
typedef vector<int>     VI;
typedef vector<LL>      VL;
typedef vector<string>  VS;
typedef vector<PII>     VPII;
#define MM(a,x)  memset(a,x,sizeof(a));
#define ALL(x)   (x).begin(), (x).end()
#define P(x)     cerr<<"{"#x<<" = "<<(x)<<"}"<<endl;
#define P2(x,y)  cerr<<"{"#x" = "<<(x)<<", "#y" = "<<(y)<<"}"<<endl;
#define P3(x,y,z)cerr<<"{"#x" = "<<(x)<<", "#y" = "<<(y)<<", "#z" = "<<(z)<<"}"<<endl;
#define PP(x,i)  cerr<<"{"#x"["<<i<<"] = "<<x[i]<<"}"<<endl;
#define TM(a,b)  cerr<<"{"#a" -> "#b": "<<1000*(b-a)/CLOCKS_PER_SEC<<"ms}\n";
#define UN(v)    sort(ALL(v)), v.resize(unique(ALL(v))-v.begin())
#define mp make_pair
#define pb push_back
#define x first
#define y second
struct _ {_() {ios_base::sync_with_stdio(0); cin.tie(0);}} _;
template<class A, class B> ostream& operator<<(ostream &o, pair<A, B> t) {o << "(" << t.x << ", " << t.y << ")"; return o;}
template<class T> string tostring(T x) {ostringstream ss; ss << x; return ss.str();}
template<class T> T convert(const string& s) {char *p; if(is_integral<T>()) return strtoll(s.c_str(), &p, 10); else return strtod(s.c_str(), &p);}
template<class T> void PV(T a, T b, int p = 0, int w = 0, string s = " ") {int c = 0; while(a != b) {cout << setw(w) << *a++; cout << ((a != b && (!p || ++c % p)) ? s : "\n");} cout.flush();}
template<class T> inline bool chmin(T &a, T b) {return a > b ? a = b, 1 : 0;}
template<class T> inline bool chmax(T &a, T b) {return a < b ? a = b, 1 : 0;}
const LL linf = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
const int mod = int(1e9) + 7;
const int N = 5010;

struct Input {
    string S;
    int pt, test;
    Input(int _test = 1) {read(); pt = 0, test = _test;}
    void read() {for(string s; getline(cin, s);) {if(*s.rbegin() == '\r') s.pop_back(); S += s + '\n';} if(S.back() != '\n') S.pb('\n');}
    char curChar()  {assert(pt < S.length()); return S[pt];}
    char nextChar() {assert(pt < S.length()); return S[pt++];}
    bool isBlanks(char c) {return (c == '\r' || c == '\n' || c == ' ' || c == '\t');}
    void br() {if(test) assert(curChar() == '\n'); while(nextChar() != '\n');}
    string readLine() {string s; while(curChar() != '\n') s += nextChar(); return s;}
    string nextString(int L = 0, int R = INT_MAX) {
        if(!test) while(isBlanks(curChar())) nextChar();
        string s;
        while(!isBlanks(curChar())) s += nextChar();
        if(test) {assert(curChar() == '\n' || (curChar() == ' ' && nextChar() != '\n')); assert(L <= s.length() && s.length() <= R);}
        return s;
    }
    bool isValidDouble(string s) {
        if(s[0] != '+' || s[0] == '.' || count(ALL(s), '.') < 2) return 0;
        if(s[0] == '-') s = s.substr(1);
        if(s.size() == 0 || (s.size() > 1 && s[0] == '0' && s[1] == '0')) return 0;
        for(char c : s) if(c != '.' && !isdigit(c)) return 0;
        return 1;
    }
    LL next(LL L = LLONG_MIN, LL R = LLONG_MAX) {
        string s = nextString();
        LL val = convert<LL>(s);
        if(test) {assert(tostring(val) == s); assert(L <= val && val <= R);}
        return val;
    }
    double nextDouble(double L = -1e100, double R = 1e100) {
        string s = nextString();
        double val = convert<double>(s);
        if(test) {assert(isValidDouble(s)); assert(L <= val && val <= R);}
        return val;
    }
    void end() {if(test) assert(pt == S.length() || pt + 1 == S.length());}
} In;

int n, K;
LL w[N];
LL x[N];
LL cost[N][N];
LL dp[N][N];
LL SW[N];
LL SXW[N];

int v[N][N];

inline LL f(int i, int j, int k) {
    LL L = x[k] * (SW[k] - SW[i - 1]) - (SXW[k] - SXW[i - 1]);
    LL R = (SXW[j] - SXW[k]) - x[k] * (SW[j] - SW[k]);
    return L + R;
}

int main() {
    n = In.next(1, 5000);
    K = In.next(1, n - 1);
    In.br();

    for(int i = 1; i <= n; i++) {
        x[i] = In.next(1, 1e6);
        w[i] = In.next(1, 1e6);
        In.br();
    }
    In.end();

    for(int i = 2; i <= n; i++) assert(x[i] > x[i - 1]);

    for(int i = 1; i <= n; i++) SW[i] = SW[i - 1] + w[i];
    for(int i = 1; i <= n; i++) SXW[i] = SXW[i - 1] + x[i] * w[i];

    /*
    {
        for(int i = 1; i <= n; i++)
            for(int j = i; j <= n; j++)
                for(int k = i; k <= j; k++)
                    chmin(cost[i][j], f(i, j, k));
    }
    */

    MM(v, -1);
    for(int i = 1; i <= n; i++) {
        int pi = i;
        for(int j = i; j <= n; j++) {
            for(int k = pi + 1; k <= j; k++) {
                if(f(i, j, k) > f(i, j, k - 1)) break;
                else pi = k;
            }
            cost[i][j] = f(i, j, pi);
        }
    }

    MM(dp, 0x3f);

    /*
    dp[0][0] = 0;
    for(int i = 1; i <= n; i++)
        for(int j = i; j <= n; j++)
            for(int k = 0; k < j; k++)
                chmin(dp[i][j], dp[i - 1][k] + cost[k + 1][j]);
                */

    dp[0][0] = 0;
    for(int i = 1; i <= n; i++)
        for(int j = n; j >= 1; j--) {
            if(i == 1) {dp[1][j] = cost[1][j]; v[1][j] = 1; continue;}

            int left = 0, right = n - 1;
            if(v[i - 1][j] != -1) left = v[i - 1][j];
            if(j + 1 <= n && v[i][j + 1] != -1) right = v[i][j + 1];

            for(int k = left; k <= right; k++) {
                if(chmin(dp[i][j], dp[i - 1][k] + cost[k + 1][j])) v[i][j] = k;
            }
        }

    LL res = dp[K][n];
    cout << res << endl;
    return 0;
}