#include #include using namespace std; // 575 const int64_t INF2 = 9223372036854775807; // 2^50-1、使わない辺とかに用いる int main() { int64_t N, M, A, B; cin >> N >> M >> A >> B; int64_t dp[3] = {max(max(M * A, (M - 1) * A + B), B), -INF2, -INF2}; while (--N) { cin >> A >> B; dp[2] = max(max(dp[0], dp[1]), dp[2]); dp[1] = max(dp[0], dp[1]) + max(A, B); dp[0] = dp[0] + max(max(M * A, (M - 1) * A + B), B); } cout << max(max(dp[0], dp[1]), dp[2]) << endl; return 0; }