#include <iostream>
#include <algorithm>
#include <stack>
#include <cstring>
#include <vector>
#include <queue>
#include <climits>

typedef long long ll;
using namespace std;

struct Node {
    int h, w;
};
vector<Node> nums;
vector<bool> take_out;
vector<vector<int>> dp;

bool cmp(Node n1, Node n2) {
    return n1.h < n2.h;
}

// 在n 剩余可拿k本书的最小值
int f(int n, int k) {
    if (n <= 1) {
        return 0;
    }
    int ans = INT_MAX;
    if (dp[n][k] != -1) return dp[n][k];
    for (int i = 0; i <= k; ++i) {
        // 拿走第 n - i 本
        int t = abs(nums[n].w - nums[n - i - 1].w);
        // 如果删的不是最后一个，那么值就为0
        if (n - i == 1) {
            ans = 0;
        }
        ans = min(ans, t + f(n - i - 1, k - i));
    }
//    cout << n << " " << k << " " << ans << endl;
    dp[n][k] = ans;
    return ans;
}

int main() {
    int n, k;
    cin >> n >> k;
    nums.resize(n + 1);
    take_out.resize(n + 1, false);
    dp.resize(n + 1, vector<int>(k + 1, -1));
    for (int i = 1; i <= n; ++i) {
        Node node;
        cin >> node.h >> node.w;
        nums[i] = node;
    }
    sort(nums.begin() + 1, nums.end(), cmp);
    cout << min(f(n, k), f(n - 1, k - 1));
}
/**
 *
3 1
1 9
2 999
3 99999

3 1
1 2
2 10
3 5
*/