CF1155D Beautiful Array

NaCly_Fish 给了你一个长度为 $n$ 的序列。 她想知道这个序列最大的美丽程度。 同时，她给了你一次操作的机会，你需要选择序列的一个子串，将其中所有数乘上 NaCly_Fish 给定的一个常数 $x$。 我们定义一个序列的美丽程度为其所有子串的和的最大值，而子串则是序列的一个连续子序列，在本题中，子串可以是空的。

第一行包括了两个整数 $n,x$，满足 $1\le n\le3\times10^5$，且$-100\le x\le100$。 之后一行包括了 $n$ 个整数 $a_i$，表示题中所给的序列，满足 $-10^9\le a_i\le10^9$。

输出一行一个整数，表示这个序列进行操作后的美丽程度。

In the first test case we need to multiply the subarray \[-2, 1, -6\], and the array becomes \[-3, 8, 4, -2, 12\] with beauty 22 (\[-3, 8, 4, -2, 12\]). In the second test case we don't need to multiply any subarray at all. In the third test case no matter which subarray we multiply, the beauty of array will be equal to 0.