#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;
using ll = long long;
int N;
ll K;
vector<ll> H, C;
ll best = numeric_limits<ll>::max();
void dfs(const vector<int>& order, int pos, vector<ll>& currentL, vector<int>& childCount, ll costSoFar) {
if (pos == order.size()) {
best = min(best, costSoFar);
return;
}
int cur = order[pos];
for (int j = 0; j < pos; j++) {
int par = order[j];
ll newL = max(H[cur], currentL[par] + 1);
ll embankCost = K * (newL - H[cur]);
ll extraExtCost = (childCount[par] >= 1 ? C[par] : 0);
ll oldL = currentL[cur];
int oldChild = childCount[par];
currentL[cur] = newL;
childCount[par]++;
dfs(order, pos + 1, currentL, childCount, costSoFar + embankCost + extraExtCost);
childCount[par] = oldChild;
currentL[cur] = oldL;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> K;
H.resize(N);
C.resize(N);
for (int i = 0; i < N; i++){
cin >> H[i] >> C[i];
}
for (int hotel = 0; hotel < N; hotel++) {
vector<int> order;
order.push_back(hotel);
for (int i = 0; i < N; i++) {
if (i == hotel) continue;
order.push_back(i);
}
do {
vector<ll> currentL(N, 0);
vector<int> childCount(N, 0);
currentL[order[0]] = H[order[0]];
dfs(order, 1, currentL, childCount, 0);
} while (next_permutation(order.begin() + 1, order.end()));
}
cout << best << "\n";
return 0;
}
