#include using namespace std; #define ALL(x) x.begin(),x.end() #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<bool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(b ostream &operator<<(ostream &os,const pair&p){ os< ostream &operator<<(ostream &os,const vector&v){ for(int i=0;i<(int)v.size();i++) os< istream &operator>>(istream &is,pair&p){ is>>p.first>>p.second; return is; } template istream &operator>>(istream &is,vector&v){ for(T &x:v)is>>x; return is; } signed main(){ int n,m;cin>>n>>m; vector a(n),b(n); rep(i,n) cin>>a[i]>>b[i]; vector> dp(n+1,vector(3,-LINF)); dp[0][0]=0; rep(i,n){ chmax(dp[i+1][0],dp[i][0]+max({b[i],a[i]*(m-1)+b[i],a[i]*m})); chmax(dp[i+1][1],dp[i][0]+a[i]); chmax(dp[i+1][1],dp[i][0]+b[i]); chmax(dp[i+1][1],dp[i][1]+a[i]); chmax(dp[i+1][1],dp[i][1]+b[i]); chmax(dp[i+1][2],max({dp[i][0],dp[i][1],dp[i][2]})); } cout<