#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()

typedef long long ll;
typedef long double ld;

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

int d, k;
vector<ll> clusters, assigned[A];
vector<pair<pair<ll, ll>, int>> points;

int mn, mx;

int randy(){
    return (rand() % (mx - mn + 1)) + mn;
}

ll minimize(){

    sort(all(clusters));

    // for(auto x : clusters)
    //  cout << "cluster " << x << endl;

    for(int i = 0; i < d; ++i){
        int bst = lower_bound(all(clusters), points[i].first.first) - clusters.begin();
        if(bst == clusters.size())
            bst--;
        if(bst - 1 >= 0 && abs(points[i].first.first - clusters[bst - 1]) < abs(points[i].first.first - clusters[bst]))
            bst--;

        bst = max(0, bst);

        if(bst > 255) throw runtime_error("FAILED");

        points[i].second = bst;

        assigned[bst].push_back(i);

        //cout << i << "  " << bst << endl;
    }


    for(int i = 0; i < k; ++i){

        if(assigned[i].size()){

            ll tot = 0, pixels = 0;

            for(auto x : assigned[i]){
                pixels += points[x].first.second;
                tot += points[x].first.second * points[x].first.first;
            }

            tot /= pixels;
            clusters[i] = tot;
        }
        else
            clusters[i] = randy();

        assigned[i].clear();
    }


    ll ans = 0;
    for(int i = 0; i < d; ++i){
        ll tt = abs(points[i].first.first - clusters[points[i].second]);
        tt *= tt;
        ans += points[i].first.second * tt;
    }

    return ans;
}


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);


    cin >> d >> k;


    points.resize(d);
    clusters.resize(k);

    for(int i = 0; i < d; ++i){
        int r, p;
        cin >> r >> p;
        points[i] = make_pair(make_pair(r, p), 0);
    }

    mn = points[0].first.first;
    mx = points[d - 1].first.first;

    srand(time(0));

    for(int i = 0; i < k; ++i){
        clusters[i] = randy();
    }

    ll a = minimize();
    ll b = minimize();

    while(a > b){
        a = minimize();
        b = minimize();
    }

    cout << a << endl;

    return 0;
}