#include<bits/stdc++.h> using namespace std; #define int int64_t #define pb push_back const int lim=510; int dp[lim][lim]{}; signed main(){ int n,k; cin>>n>>k; vector<int>process; map<int,int>cnt,mn; for(int i=0;i<n;i++){ int x,y; cin>>x>>y; cnt[x]++; if(!mn.count(x)){ mn[x]=y; }else{ mn[x]=min(mn[x],y); } process.pb(x); } process.pb(INT_MAX); sort(process.begin(),process.end()); process.resize(unique(process.begin(),process.end())-process.begin()); int m=process.size(); int prefbest[m]; prefbest[0]=LLONG_MAX; for(int i=0;i<m;i++){ if(i){ prefbest[i]=min(prefbest[i-1],mn[process[i-1]]); } } for(int i=0;i<=n;i++){ for(int j=0;j<=n;j++){ dp[i][j]=LLONG_MAX; } } dp[1][cnt[process[0]]-1]=0; auto print=[&](){ for(int i=0;i<=n;i++){ for(int j=0;j<=n;j++){ cerr<<(dp[i][j]==LLONG_MAX?-1:dp[i][j])<<' '; }cerr<<'\n'; }cerr<<'\n'; }; for(int i=1;i<m;i++){ int x=i&1; for(int save=0;save<=n;save++){ for(int tolift=1;tolift<process[i]-process[i-1];tolift++){ int ch=0; for(int have=0;have<n;have++){ if(dp[save][have]==LLONG_MAX)continue; if(dp[save][have]+tolift*k<dp[save][have-1]){ dp[save][have-1]=dp[save][have]+tolift*k; ch=1; } } if(!ch)break; } } if(process[i]-process[i-1]!=1){ int ch; do{ ch=0; for(int save=0;save<n;save++){ for(int have=1;have<=n;have++){ if(dp[save][have]==LLONG_MAX)continue; if(dp[save][have]+k+prefbest[i]<dp[save+1][have-1]){ dp[save+1][have-1]=dp[save][have]+k+prefbest[i]; ch=1; } } } }while(ch); } // print(); if(i!=m-1){ int cc=cnt[process[i]]; for(int save=0;save<=n;save++){ for(int have=n;n-cc<have;have--){ dp[save][have]=LLONG_MAX; } for(int have=n-cc;0<=have;have--){ if(dp[save][have]==LLONG_MAX)continue; dp[save][have+cc]=dp[save][have]+k*(process[i]-process[i-1])*have; dp[save][have]=LLONG_MAX; } } for(int save=0;save<=n;save++){ for(int have=1;have<=n;have++){ if(dp[save][have]==LLONG_MAX)continue; dp[save][max<int>(0,have-save)]=dp[save][have]; dp[save][have]=LLONG_MAX; } } for(int have=n;have;have--){ for(int save=0;save<n;save++){ if(dp[save][have]==LLONG_MAX)continue; if(dp[save][have]+prefbest[i]<dp[save+1][have-1]){ dp[save+1][have-1]=dp[save][have]+prefbest[i]; } } } } // print(); } int ans=LLONG_MAX; for(int i=0;i<=n;i++){ ans=min(ans,dp[i][0]); } cout<<ans<<'\n'; }