思路：动态规划

以下思路考场能AC，但是有点问题。

定义$dp[i][j][0]$代表$a[i,...,j]$中连续子段的最小值

定义$dp[i][j][1]$代表$a[i,...,j]$中连续子段的最大值

可以采用二维循环求出dp数组。

之后枚举小乖选择哪个子段，然后计算这个子段情况下小坏所能达到的最小贡献，并取最大值即为最终答案。

小乖和小坏在玩一个游戏，游戏中有一个长度为 $n$ 的数组$a_1,a_2,...,a_n$ 和一个固定的整数$k$。游戏规则如下，双方都会执行最优策略:

第一步,小乖选择一个非空的区间 $[l, r]$，将这个区间中的所有数字都乘上 $k$。

第二步, 小坏选择一个非空的区间 $[l, r]$, 将这个区间中的所有数字都乘上 $k$。

记$sum=\sum\limits_{i=1}^n a_i$ 小坏想让$sum$尽可能小，小乖想让$sum$尽可能大，你需要求出最后 $sum$ 的值。

输入描述

第一行输入两个整数 n 和 k$(10^{-5} ≤ k ≤ 10^5, 1 ≤ n ≤ 1000; -10^5 ≤ a_i ≤ 10^5)$,代表数组长度和固定的整数。

第二行输入 $n$ 个整数 $a_1, a_2, ..., a_n$, $(-10^5≤ a_i ≤10^5)$代表数组。

输出描述

在一行上输出一个整数表示答案。

示例 1

输入

6 2
-1 -2 -3 1 2 3

输出

0

说明

小乖会选择区间$[4, 6]$,数组变成{$-1,-2,-3,2,4,6$}；

小坏会选择区间$[1,3]$,数组变成{$-2,-4,-6,2,4,6$}；

数组总和为 $0$。