题目内容

给定一个长度为 $n$ 的整数序列 $A = [a_1, a_2, \dots, a_n]$ 和一个整数 $c$。两位玩家先后进行操作，每人选择一个非空区间，将区间内所有元素乘上 $c$。先手想让操作结束后序列的元素总和尽可能大，后手想让总和尽可能小。双方都采取最优策略。请问最终序列的元素总和是多少？

序列长度 $n$ 不超过 $1000$，所有元素 $a_i$ 的绝对值不超过 $10^5$，系数 $c$ 的绝对值不超过 $10^5$。

输入描述

第一行包含两个整数 $n$ 和 $c$ $(1 \le n \le 1000, |c| \le 10^5)$。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(|a_i| \le 10^5)$，表示初始序列。

输出描述