CF1155D.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.

给你一个包含 $n$ 个整数的数组 $a$。数组的“美感”（beauty）定义为该数组中某个连续子数组（该子数组可以为空）元素之和的最大值。例如，数组 [10, -5, 10, -4, 1] 的美感为 15；而数组 [-3, -5, -1] 的美感为 0。

你可以至多选择 $a$ 中的一个连续子数组，并将其中所有元素乘以 $x$。你希望在至多执行一次该操作后，使数组的美感最大化。

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$.

第一行包含两个整数 $n$ 和 $x$（$1 \le n \le 3 \cdot 10^5$，$-100 \le x \le 100$）—— 分别表示数组 $a$ 的长度和整数 $x$。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^9 \le a_i \le 10^9$）—— 即数组 $a$。

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

输出一个整数——在将子数组 $x$ 中的所有值乘以某个数后，数组 $a$ 可能达到的最大美观度。

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.

在第一个测试用例中，我们需要对子数组 [-2, 1, -6] 进行乘法操作，数组变为 [-3, 8, 4, -2, 12]，其美观度为 22（即 [-3, 8, 4, -2, 12]）。

在第二个测试用例中，我们完全不需要对任何子数组进行乘法操作。

在第三个测试用例中，无论选择哪个子数组进行乘法操作，数组的美观度都等于 0。