#include "bits/stdc++.h" #define in std::cin #define out std::cout #define rep(i,N) for(LL i=0;iA, B; std::vector>memo; LL dp(LL i, LL j) { if (i == -1) return (j == 0 ? -inf : 0); if (memo[i][j] != -1) return memo[i][j]; LL res; if (j == 0) { LL res1 = dp(i - 1, 0); LL res2 = dp(i - 1, 1) + std::max(A[i], B[i]); LL res3 = dp(i - 1, 2) + std::max({ A[i] * M, A[i] * (M - 1) + B[i] }); res = std::max({ res1, res2, res3 }); } if (j == 1) { LL res1 = dp(i - 1, 1) + std::max(A[i], B[i]); LL res2 = dp(i - 1, 2) + std::max({ A[i] * M, A[i] * (M - 1) + B[i] }); res = std::max(res1, res2); } if (j == 2) res = dp(i - 1, 2) + std::max({ A[i] * M, A[i] * (M - 1) + B[i], B[i] }); return memo[i][j] = res; } int main() { in >> N >> M; A.resize(N); B.resize(N); rep(i, N) in >> A[i] >> B[i]; memo.resize(N + 1, std::vector(5, -1)); out << dp(N - 1, 0) << std::endl; }