kaveh

// IN THE NAME OF ALLAH.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define pb push_back

const int N = 257;
int dp[N][N][N], a[N];


int32_t main(){
	ios::sync_with_stdio(false);

	int d, k;
	cin >> d >> k;
	for(int i = 0; i < d; i++){
		int c, e;
		cin >> c >> e;
		a[c] = e;
	}

	for(int i = 0; i < N; i++){
		for(int j = 1; j <= i + 1; j++){
			for(int l = j - 1; l < i; l++)
				dp[i][j][l] = dp[i - 1][j][l] + a[i] * (i - l) * (i - l);
			if(j == 1){
				for(int l = 0; l < i; l++)
					dp[i][j][i] += a[l] * (i - l) * (i - l);
			}
			else{
				int cost = 0;
				dp[i][j][i] = dp[i - 1][j - 1][i - 1];

				for(int l = i - 1; 2 * l >= i; l--){

					cost += a[l] * (i - l) * (i - l);
					dp[i][j][i] = min(dp[i][j][i], dp[l - 1][j - 1][2 * l - i] + cost);
					if(2 * l - 1 >= i)
						dp[i][j][i] = min(dp[i][j][i], dp[l - 1][j - 1][2 * l - i - 1] + cost);
				}
			}
		}
	}

	int ans = dp[N - 1][k][k - 1];
	for(int i = k; i < N; i++)
		ans = min(ans, dp[N - 1][k][i]);
	cout << ans << '\n';
	return 0;
}