#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <cstring>
#include <list>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <unordered_map>
#include <cmath>
#include <climits>
#include <bitset>
using namespace std;
struct Node {
	int h; int b;
	bool operator<(const Node& b) const {
		return this->h < b.h;
	}
};
int dp[105];
int pre[105];
int n, k;
Node arr[105];
int main() {
	for (int i = 2; i < 105; i++) dp[i] = 0x3f3f3f3f;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i].h >> arr[i].b;
	}
	sort(arr, arr + n + 1);
	for (int i = 1; i <= n; i++) {
		for (int j = i; j >= 1; j--) {
			if (dp[j - 1] + abs(arr[i].b - pre[i]) < dp[j]) {
				if (j - 1 != 0) {
					dp[j] = dp[j - 1] + abs(arr[i].b - pre[j - 1]);
					pre[j] = arr[i].b;
				}
				else {
					pre[j] = arr[i].b;
				}
			}
		}
	}
	cout << dp[n - k];
}

dp[i][j] 代表前i个书，中挑选j个的最小整齐度