#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define pb push_back #define ff first #define ss second #define INF 1000000001LL #define POT (1LL<<20) #define INFL 1000000000000000099LL #define pii pair<ll,ll> #define ppi pair<pii,ll> #define pip pair<ll,pii> #define ppp pair<pii,pii> #define vi vector<ll> #define vii vector<pii> #define vvi vector<vi> #define al(x) x.begin(),x.end() #define rev(x) reverse(al(x)) #define X 18 #define FCTCST 7 template<typename T, typename U> pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) { return {a.first + b.first, a.second + b.second}; } template<typename T, typename U> pair<T, U> operator-(const pair<T, U>& a, const pair<T, U>& b) { return {a.first - b.first, a.second - b.second}; } template<typename T, typename U,typename Z> pair<T, U> operator*(const pair<T, U>& a, const Z& b) { return {a.first*b, a.second*b}; } template<typename T, typename U,typename Z> pair<T, U> operator/(const pair<T, U>& a, const Z& b) { return {a.first/b, a.second/b}; } template<typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os<<"{"<<p.ff<<", "<<p.ss<<"}"; return os; } template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) { os << "{"; for (size_t i = 0; i < v.size(); ++i) { if (i) os << ", "; os << v[i]; } os << "}"; return os; } template<ll MOD=998244353> struct mint_t{ ll x; mint_t(ll y=0){x=y%MOD;if(x<0)x+=MOD;} mint_t& operator+=(const mint_t& a){if((x+=a.x)>=MOD)x-=MOD;return *this;} mint_t& operator-=(const mint_t& a){if((x+=MOD-a.x)>=MOD)x-=MOD;return *this;} mint_t operator+(const mint_t& a)const{mint_t res(*this);return res+=a;} mint_t operator-(const mint_t& a)const{mint_t res(*this);return res-=a;} mint_t& operator*=(const mint_t& a){(x*=a.x)%=MOD;return *this;} mint_t operator*(const mint_t& a)const{mint_t res(*this);return res*=a;} mint_t fp(ll y)const{ mint_t a=1,b=x; while(y){ if(y&1)a*=b; b*=b; y/=2; } return a; } mint_t& operator/=(const mint_t& a){(*this)*=a.fp(MOD-2);return *this;} mint_t operator/(const mint_t& a)const{mint_t res(*this);return res/=a;} }; #define mint mint_t<> template<long long MOD> istream& operator>>(istream& in, mint_t<MOD>& a){ ll x; in>>x; a=mint_t<MOD>(x); return in; } template<long long MOD> istream& operator<<(istream& out, mint_t<MOD>& a){ out<<a.x; return out; } mint fct[FCTCST]; mint bnm(ll a,ll b){ if(b>a || a<0)return 0; return fct[a]/fct[b]/fct[a-b]; } ll dp[301][301],dp2[301][301];//ile mam darmowych, ile wysylam vii v; vi v2; ll n,k,a,b; ll gtmn(ll x){ ll mn=INFL; for(ll i=0;i<n;i++)if(v[i].ff<x)mn=min(mn,v[i].ss); return mn; } map<ll,ll>il; void solve(){ cin>>n>>k; for(ll i=0;i<n;i++){ cin>>a>>b; v.pb({a,b}); v2.pb(a); } sort(al(v2)); for(ll i=1;i<n;i++)if(v2[i]<=v2[i-1])v2[i]=v2[i-1]+1; sort(al(v)); ll cnst=0; for(ll i=1;i<n;i++)if(v[i].ff==v[0].ff)v[i].ff++,cnst+=k; for(ll i=1;i<n;i++)il[v[i].ff]++; for(ll i=0;i<301;i++)for(ll j=0;j<301;j++)dp[i][j]=INFL; dp[1][il[v2[0]+1]]=cnst; for(ll i=1;i<n;i++)v2.pb(v2[i]-1); sort(al(v2)); v2.erase(unique(al(v2)),v2.end()); v2.erase(v2.begin()); for(ll i:v2){ for(ll j=0;j<301;j++)for(ll m=0;m<301;m++)dp2[m][j]=INFL; ll pm=il[i+1],mn=gtmn(i); for(ll j=1;j<=n;j++){ for(ll m=il[i];m<=n;m++){ if(m<=j){ dp2[j][pm]=min(dp2[j][pm],dp[j][m]); } else{ dp2[j][pm+m-j]=min(dp2[j][pm+m-j],dp[j][m]+(m-j)*k); } } for(ll m=n;m>pm;m--){ dp2[j+1][m-1]=min(dp2[j+1][m-1],dp2[j][m]-k+mn); } } swap(dp,dp2); } ll bs=INFL; for(ll i=1;i<=n;i++)bs=min(bs,dp[i][0]); cout<<bs; } int main(){ fct[0]=1; for(ll i=1;i<FCTCST;i++)fct[i]=fct[i-1]*i; ll t=1; //cin>>t; for(ll i=1;i<=t;i++){ //cout<<"Case #"<<i<<": "; solve(); } }