序列

题目描述

给定一个长度为 $n$ 的序列 $a$，你需要求出所有子段中和最大的那个是多少。

Dave 有一次修改机会：他有一个值 $x$，可以将序列的一个子段中所有元素都乘上 $x$。

请问 Dave 修改后能获得的最大子段和是多少？

请注意，上面描述的所有子段都可以为空。

输入格式

输入一行两个整数 $n,x$。

接下来一行 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

输出格式

一行一个整数，表示 Dave 操作后能获得的最大子段和。

数据范围

• 对于 $60\%$ 的数据，$n \leq 10^3$
• 对于 $100\%$ 的数据，$1 \leq n \leq 3 \times 10^5, -10^5 \leq a_i,x \leq 10^5$

样例数据 1

输入

5 -2
-3 8 -2 1 -6

输出

22