题目描述

大家都知道最大子段和问题。具体的，给定一个长度为 $n$ 的序列 $a$，你需要求出整个序列所有子段中和最大的那个是多少。

当然如果只是这样就太无聊了。于是 Dave 告诉你他有一次修改这个序列的机会。具体的，他有一个值 $x$，他可以将序列的一个子段中所有元素都乘上 $x$。

Dave 自然想让最大子段和最大。那么请问 Dave 修改后能获得的最大子段和的和是多少？

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

输入格式

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

接下来一行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，意义如上。

输出格式

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

5 -2
-3 8 -2 1 -6

22

数据范围

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