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$。 ### 输出格式 输出一行一个整数，表示这个序列进行操作后的美丽程度。

题目描述

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

输入输出样例

输入样例 #1

5 -2
-3 8 -2 1 -6

输出样例 #1

22

输入样例 #2

12 -3
1 3 3 7 1 3 3 7 1 3 3 7

输出样例 #2

42

输入样例 #3

5 10
-1 -2 -3 -4 -5

输出样例 #3

0

说明

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.