A12468 | Beautiful Array

You are given an array $a$ consisting of $n$ integers. Beauty of array is the maximum sum of some consecutive subarray of this array (this subarray may be empty). For example, the beauty of the array \[10, -5, 10, -4, 1\] is 15, and the beauty of the array \[-3, -5, -1\] is 0.

You may choose at most one consecutive subarray of $a$ and multiply all values contained in this subarray by $x$ . You want to maximize the beauty of array after applying at most one such operation.

The first line contains two integers $n$ and $x$ ( $1 \le n \le 3 \cdot 10^5, -100 \le x \le 100$ ) — the length of array $a$ and the integer $x$ respectively.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $-10^9 \le a_i \le 10^9$ ) — the array $a$ .

Print one integer — the maximum possible beauty of array $a$ after multiplying all values belonging to some consecutive subarray $x$ .