#include #include using namespace std; // 575 const int64_t INF = 4611686018427387903; // 10^62-1、使わない辺とかに用いる const int MAX = 100001; // 配列長 int main() { int64_t N, M, A, B; cin >> N >> M; static int64_t cumsum[MAX], cumsum2[MAX]; cumsum[0] = cumsum2[0] = 0; for (int i = 1;i <= N;++ i) { cin >> A >> B; cumsum[i] = cumsum[i - 1] + max(max(A, B) + (M - 1) * A, B); cumsum2[i] = cumsum2[i - 1] + max(A, B); } int64_t ans = -INF; for (int i = 1;i <= N;++ i) { // i: 毎日選ぶ範囲 (0, i]が毎日選ばれる for (int j = i;j <= N;++ j) { // j: 1日選ぶ範囲 (i, j]が1日だけ選ばれる ans = max(ans, cumsum[i] + (cumsum2[j] - cumsum2[i])); } } cout << ans << endl; return 0; } /* 31536000のコメント解説欄 ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー 一応、O(N^2)の確認を 毎日/1日/選ばない、の3通りがこの順に出るので、仕切りを2か所決め打つ この時のコストは累積和からO(1)で計算できるので、それを用いる */