题目背景

原题链接：https://oier.team/problems/X8B。

---

那是，深藏的思念
那是，永恒的誓言
那是，真心的祈愿
那是，悔恨的心怀
那是，童年的约定——

终将改变之物，与永不改变之物。

题目描述

Anzu 有一个正整数数列 $a_1, \ldots, a_n$ 和一个整数 $x$。她可以进行至多一次操作，选择一对正整数 $1 \le l \le r \le n$，然后对于所有 $l \le i \le r$ 的正整数 $i$ 让 $a_i$ 变成 $x$。现在她想要知道，在这之后，数列里所有数的和最大是多少。

输入格式

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

第二行，$n$ 个正整数 $a_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

提示

【样例解释 #1】

最优的策略是选择 $l=3$，$r=4$ 进行一次操作，此时数列变为 $[1,4,2,2,5]$，总和为 $14$。

【样例解释 #2】

最优的策略为选择 $l=1$，$r=7$ 进行一次操作。

【样例解释 #3】

最优的策略为不进行操作。

【数据范围】

对于 $30\%$ 的数据，$n \le 500$。

对于另外 $20\%$ 的数据，$n \le 3 \times 10^3$。

对于另外 $10\%$ 的数据，$x=0$。

对于所有数据，保证 $1 \le n \le 10^5$，$1 \le a_i \le 10^9$，$0 \le x \le 10^9$。