Sum Problem PLUS

Since the previous version is too simple,Captain Huang has a fun idea to improve it. She will give an array consisting of n integers. You need to calculate the maximum sum of some consecutive subarray of this array (this subarray may be empty) which called the beauty of array. 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. To be more interesting, you may choose at most one consecutive subarray and multiply all values contained in this subarray by x. Your task is to maximize the beauty of array after applying at most one such operation. (Pay attention to memory！)

The first line contains two integers n and x (1<=n<=3e5, -100<=x<=100) — the length of array and the integer x respectively.

The second line contains n integers a1, a2 , …, an (−1e9≤ai≤1e9) — the array.

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

5 -2
-3 8 -2 1 -6

22