#ifndef LOCAL #pragma GCC Optimize("O3,Ofast,unroll-loops") #pragma GCC Target("bmi,bmi2,avx,avx2") #endif #include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; #define int ll #define f first #define s second #define mp make_pair #define pb push_back #define pii pair<int, int> #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin() (x).rend() #define relax(x, y) (x) = min((x), (y)); #ifndef LOCAL #define endl "\n" #endif mt19937 rnd(11); void solve() { int n, k; cin >> n >> k; vector<pii> a(n); int H = 0; int mn = 1e9; for (auto &x : a) { cin >> x.f >> x.s; H = max(H, x.f); mn = min(mn, x.f); } H -= mn; H = H * 2 + 30; for (auto &x : a) { x.f -= mn; } vector<int> c(H, 1e18); vector<int> g(H); for (auto &x : a) { ++g[x.f]; c[x.f] = min(c[x.f], x.s); } for (int i = 0; i < H - 1; ++i) { c[i + 1] = min(c[i + 1], c[i]); } int dp[H][n + 1][n + 1]; for (int i = 0; i < H; ++i) { for (int j = 0; j <= n; ++j) { for (int k = 0; k <= n; ++k) { dp[i][j][k] = 1e18; } } } dp[0][1][g[0] - 1] = (g[0] - 1) * k; for (int i = 1; i < H; ++i) { for (int q = 0; q <= n; ++q) { for (int in = 0; in <= n - g[i]; ++in) { for (int out = 0; out <= in + g[i]; ++out) { int r = in + g[i] - out; relax(dp[i][max(r, q)][out], dp[i - 1][q][in] + max(r - q, 0ll) * c[i - 1] + k * out); } } } } int ans = 1e18; for (int c = 0; c <= n; ++c) { ans = min(ans, dp[H - 1][c][0]); } cout << ans << endl; } signed main() { #ifdef LOCAL freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #else ios::sync_with_stdio(false); cin.tie(0); #endif int t = 1; // cin >> t; while (t--) { solve(); } }