#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define inf (long long) 1e18

typedef long long ll;
typedef long double ld;

const int N = 123456;
const int M = 1234567;
const int P = 400004;
const int A = 256;

const int n = 257;

int a[n + 2];
long long bstInBetween[n + 2][n + 2];
long long dp[n + 2][n + 2];

int main(int argc, char const *argv[])
{

    #ifdef Cyborg1o1
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

    cin.sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


    int d, k;
    cin >> d >> k;
    k++;

    int mx = 0;
    for(int i = 0; i < d; ++i){
        int x, y;
        cin >> x >> y;
        a[x + 1] = y;
        mx = max(mx, x + 1);
    }

    for(int i = 0; i < n; ++i){ //2nd to last v
        for(int j = i + 1; j <= n; ++j){ //last v
            for(int kk = i; kk <= j; ++kk){
                int dist = min(i == 0? n : kk - i, j >= mx + 1 ? n : j - kk);
                bstInBetween[i][j] += a[kk] * 1ll * dist * dist;
            }
            // cout << "i " << i << " j " << j << " " << bstInBetween[i][j] << endl;
        }
    }

    memset(dp, 0x7f, sizeof dp);

    dp[0][0] = 0;

    for(int i = 1; i <= mx + 1; ++i){ //possible values for vi
        for(int j = 1; j <= k && j <= i; ++j){ //cluster number
            for(int kk = i - 1; kk >= 0; --kk){ //2nd to last value vkk
                dp[i][j] = min(dp[i][j], dp[kk][j - 1] + bstInBetween[kk][i]);
            }
             // cout << "i -> j -> " << i << " " << j << " " << dp[i][j] << endl;
        }
    }

    //cout << dp[n][k] << endl;
    cout << dp[mx + 1][k] << endl;

    return 0;
}