Maximum Array Sum by Single Segment Replacement

Anzu has a sequence of positive integers \(a_1, a_2, \ldots, a_n\) and an integer \(x\). She is allowed to perform at most one operation: choose a contiguous segment defined by indices \(l\) and \(r\) (where \(1 \le l \le r \le n\)) and replace every element in that segment with \(x\). After performing at most one such operation, she wants to know the maximum possible sum of the sequence.

More formally, if the original sum of the sequence is \(S = \sum_{i=1}^n a_i\), and if she chooses a segment \([l, r]\), the change in sum is \[ \Delta = (r - l + 1) \times x - \sum_{i=l}^{r} a_i. \] She can choose to perform no operation if it does not improve the sum. Your task is to compute the maximum sum after at most one such operation.

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(x\) (where \(1 \le n \le 10^5\) and \(1 \le x \le 10^9\)).

The second line contains \(n\) positive integers \(a_1, a_2, \ldots, a_n\) separated by spaces.

outputFormat

Output a single integer representing the maximum sum of the sequence after performing at most one operation.

sample

5 6
1 2 3 4 5

30