题目描述

小可和小达玩一个冒险游戏，有 $n$ 个关卡，第 $i$ 关的得分是 $a_i$（可正可负）。他们有一个双倍积分卡，可以选一段连续的关卡 $[l, r]$，把这些关的得分都 乘以 $k$。

积分卡只能用一次，也可以不用。

问：游戏结束后，他们的总得分最多能是多少？

输入格式

第一行两个整数 $n$ 和 $k$。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

输出格式

输出一个整数，表示最高总得分。

样例

5 2
-10 10 20 30 -20

90

5 1000000
-1 -2 -3 -4 -5

-15

9 -1
-9 9 -8 2 -4 4 -3 5 -3

13

提示

样例解释

样例1：

初始总得分：$(-10) + 10 + 20 + 30 + (-20) = 30$。

选择第 2 到第 4 关使用积分卡（$k=2$）：

• 原得分：10, 20, 30
• 使用后得分：20, 40, 60

新总得分：$(-10) + 20 + 40 + 60 + (-20) = 90$。

不操作得 30 分，操作后得 90 分，最大值是 90。

样例2：

初始总得分：$(-1) + (-2) + (-3) + (-4) + (-5) = -15$。

如果不使用积分卡，初始总得分：$(-1) + (-2) + (-3) + (-4) + (-5) = -15$，这是可以达到的最大值。

数据范围

• $1 \le n \le 3 \times 10^5$
• $-10^6 \le k \le 10^6$
• $-10^6 \le a_i \le 10^6$