#include <bits/stdc++.h>
#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))
constexpr bool dbg = 1;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl
#define int long long
#define ld long double
#define pb push_back
#define rg ranges
using namespace std;
int n, k;
vector<int> h, c;
constexpr int inf = 4e18;
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> k;
h.resize(n);
c.resize(n);
rep(i, 0, n) cin >> h[i] >> c[i];
int ans = inf;
rep(vs, 0, n) {
DC << "Starting at " << vs << eol;
int mAns = -k;
vector<int> myH(n);
rep(i, 0, n) myH[i] = max(h[i], h[vs] + 1), mAns += k * (myH[i] - h[i]);
myH[vs]--;
DEBUG {
DC << " myH: ";
rep(i, 0, n) DC << myH[i] << ' ';
DC << eol;
}
DC << " At cost " << mAns << eol;
vector<int> path;
vector<pair<int, int>> v(n);
rep(i, 0, n) v[i] = {myH[i], i};
rg::sort(v);
auto it = v.begin();
DC << " Path: ";
while(it != v.end()) {
auto ch = it -> first;
pair<int, int> mn = {c[it -> second], it -> second};
while(++it != v.end() && it -> first == ch) mn = min(mn, {c[it -> second], it -> second});
path.pb(mn.second);
DC << mn.second << ' ';
}
DC << eol;
int bestLast = 0;
map<int, int> freebies;
freebies[v.back().first + 1] = 1;
repIn2(mh, i, v) {
int best = inf, bestH = inf;
repIn(j, path) {
if(j == i) best = 0;
auto me = max(myH[j] + 1 - mh, 0ll) * k + c[j];
best = min(best, me);
if(best == me) bestH = myH[j] + 1;
}
if(best) {
auto it2 = freebies.lower_bound(mh);
int xd = inf, xd2 = -1;
if(it2 != freebies.end()) {
xd = (it2 -> first - mh) * k;
xd2 = it2 -> first;
}
DC << " " << i << " costs " << best << " or " << xd << " if plugged into a freebie at " << xd2 << eol;
if(xd < best) {
it2 -> second--;
freebies[xd2 + 1]++;
if(!(it2 -> second)) freebies.erase(it2);
best = xd;
}
else freebies[bestH]++;
}
mAns += best;
}
DC << " Overall we have " << mAns + bestLast << eol << eol;
ans = min(ans, mAns + bestLast);
}
cout << ans << '\n';
}
