// author: erray
#include <bits/stdc++.h>
#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) void(37)
#endif
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int N, K;
cin >> N >> K;
vector<int> H(N), C(N);
vector<int> poses;
for (int i = 0; i < N; ++i) {
cin >> H[i] >> C[i];
poses.push_back(H[i]);
poses.push_back(H[i] + 1);
}
auto sh = H;
sort(sh.begin(), sh.end());
sort(poses.begin(), poses.end());
poses.erase(unique(poses.begin(), poses.end()), poses.end());
int s = int(poses.size());
vector<int> pref_mn(s, int(1E9));
for (int i = 0; i < N; ++i) {
int lb = int(lower_bound(poses.begin(), poses.end(), H[i]) - poses.begin());
pref_mn[lb] = min(pref_mn[lb], C[i]);
}
constexpr int64_t inf = int64_t(1e16);
vector<int64_t> mn(s);
mn[0] = inf;
for (int i = 0; i < s - 1; ++i) {
mn[i + 1] = min<int64_t>(mn[i], pref_mn[i]);
}
vector<int64_t> pref(N + 1);
for (int i = 0; i < N; ++i) {
pref[i + 1] = pref[i] + sh[i];
}
auto Ckmin = [&](int64_t& x, int64_t y) {
x = min(x, y);
};
vector<int> pt(s);
for (int i = 0; i < s; ++i) {
pt[i] = pt[i - !!i];
while (pt[i] < N && sh[pt[i]] <= poses[i]) {
++pt[i];
}
}
vector<vector<vector<int64_t>>> best(N + 1, vector<vector<int64_t>>(s + 1, vector<int64_t>(N + 1, inf)));
best[0][0][1] = 0;
for (int i = 0; i < N; ++i) {
for (int pos = 0; pos < s; ++pos) {
for (int leaf = 1; leaf <= N; ++leaf) {
int64_t me = best[i][pos][leaf];
Ckmin(best[i][pos + 1][leaf], me);
if (sh[i] > poses[pos]) {
continue;
}
if (i + leaf < N && sh[i + leaf] <= poses[pos]) {
Ckmin(best[i][pos][leaf + 1], me + mn[pos]);
}
int go = min<int64_t>(i + (pos == s - 1 ? int64_t(N) : 1LL * leaf * (poses[pos + 1] - poses[pos])), pt[pos]);
int start = poses[pos];
int need = go - i;
int last = start + (need / leaf);
auto G = [&](int x) { return 1LL * x * (x - 1) / 2; };
int64_t this_formula_will_be_fucked_up = 1LL * (need % leaf) * last + 1LL * leaf * (G(last) - G(start));
this_formula_will_be_fucked_up -= pref[go] - pref[i];
if (this_formula_will_be_fucked_up != 0 && inf / this_formula_will_be_fucked_up + 10 < K) {
continue;
}
Ckmin(best[go][pos + 1][leaf], me + K * this_formula_will_be_fucked_up);
}
}
}
int64_t ans = inf;
for (int i = 0; i <= s; ++i) {
for (int j = 0; j <= N; ++j) {
Ckmin(ans, best[N][i][j]);
}
}
cout << ans << '\n';
}
