#include <iostream>
#include <cstring>
#define min(u,v) u<v? u:v
using namespace std;
int n, m, a[1005], f[1005][1005][2], c[1005];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> c[i] >> a[i];
		a[i] += a[i - 1];
	}
	memset(f, 127, sizeof(f));
	f[m][n][0] = f[m][m][1] = 0;
	for (int j = m; j <= n; j++)
		for (int i = j - 1; i; i--) {
			f[i][j][0] = min(f[i + 1][j][0] + (a[n] - (a[j] - a[i])) * (c[i + 1] - c[i]),
			                 f[i + 1][j][1] + (a[n] - (a[j] - a[i])) * c([j] - c[i]));
			f[i][j][1] = min(f[i][j - 1][1] + (a[n] - (a[j - 1] - a[i - 1])) * (c[j] - c[j - 1]),
			                 f[i][j - 1][0] + (a[n] - (a[j - 1] - a[i - 1])) * (c[j] - c[i]));
		}
	cout << min(f[1][n][0], f[1][n][1];
	            return 0;
}