#include #include using namespace std; // 575 const int64_t INF = 3e16;//4611686018427387903; // 10^62-1、使わない辺とかに用いる int main() { int64_t N, M, A, B; cin >> N >> M >> A >> B; int64_t everyday = max(max(A, B) + A * (M - 1), B), oneday = -INF, nothanks = -INF; // 1番目の鶏は固定で選ばれる while (--N) { cin >> A >> B; nothanks = max(max(everyday, oneday), nothanks); // 選ばない oneday = max(everyday, oneday) + max(A, B); // 初日のみ everyday = everyday + max(max(A, B) + A * (M - 1), B); // 毎日選ぶ(毎日卵、最後の日だけ鶏肉、初日で殺す、の3択) } cout << max(max(everyday, oneday), nothanks) << endl; return 0; }