#1398. 【MX-X8-T1】「TAOI-3」幸运草

【MX-X8-T1】「TAOI-3」幸运草

题目描述

Anzu 有一个正整数数列 a1,…,ana_1, \ldots, a_n 和一个整数 xx。她可以进行至多一次操作,选择一对正整数 1≤l≤r≤n1 \le l \le r \le n,然后对于所有 l≤i≤rl \le i \le r 的正整数 ii 让 aia_i 变成 xx。现在她想要知道,在这之后,数列里所有数的和最大是多少。

输入格式

第一行,两个非负整数 n,xn, x。

第二行,nn 个正整数 a1,…,ana_1, \ldots, a_n。

输出格式

仅一行,一个正整数,表示答案。

样例

5 2
1 4 1 1 5
14
7 3
1 1 4 5 1 4 1
21
1 197
251
251

题目来源:洛谷 P11642