#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair P; long long int INF = 3e18; double Pi = 3.1415926535897932384626; vector G[500005]; vector

tree[500010]; priority_queue pql; priority_queue

pqp; //big priority queue priority_queue ,greater > pqls; priority_queue ,greater

> pqps; //small priority queue //top pop int dx[8]={1,0,-1,0,1,1,-1,-1}; int dy[8]={0,1,0,-1,1,-1,-1,1}; char dir[] = "DRUL"; //ll bit[500005]; //↓,→,↑,← #define p(x) cout<> n >> m; assert(1 <= n && n <= 100000); assert(1 <= m && m <= 100000); for(i=1;i<=n;i++){ cin >> x[i] >> y[i]; assert(-100000 <= x[i] && x[i] <= 100000); assert(-100000 <= y[i] && y[i] <= 100000); } for(i=1;i<=n;i++){ sc[i][0] = 0; sc[i][1] = max(x[i],y[i]); if(x[i] > 0){ sc[i][2] = max(x[i],y[i]) + x[i] * (m - 1); }else if(x[i] < 0){ sc[i][2] = max(y[i],x[i]*m); }else{ sc[i][2] = max(0ll,y[i]); } } dp[1][2] = sc[1][2]; dp[1][1] = -INF; dp[1][0] = -INF; for(i=2;i<=n;i++){ dp[i][2] = dp[i-1][2] + sc[i][2]; dp[i][1] = dp[i-1][1] + sc[i][1]; dp[i][1] = max(dp[i][1],dp[i-1][2] + sc[i][1]); dp[i][0] = dp[i-1][0] + sc[i][0]; dp[i][0] = max(dp[i][0],dp[i-1][2] + sc[i][0]); dp[i][0] = max(dp[i][0],dp[i-1][1] + sc[i][0]); for(j=0;j<3;j++){ //pe(dp[i][j]); } //el; } ans = -INF; for(i=0;i<3;i++){ ans = max(ans,dp[n][i]); } p(ans); return 0; }