题目描述

给定一个由 $n$ 个正整数构成的数列 $a_1, a_2, \dots, a_n$ 和一个整数 $x$。

你可以至多进行一次操作：选择一对正整数 $1 \le l \le r \le n$，然后将数列中第 $l$ 到第 $r$ 个位置的所有数都变为 $x$。

操作完成后，求数列所有数之和的最大值。

输入格式

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

第二行 $n$ 个正整数 $a_1, a_2, \dots, 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$，总和为 $21$。

【样例解释 #3】

不进行操作，总和为 $251$。

【数据范围】

对于 $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$。