题目描述

在数字社交媒体的浩瀚世界中，运营者小蓝负责维护一条情绪链路。这条链路由 $n$ 个用户节点依次排列而成，每个节点上记录着一个情绪值。具体地，第 $i$ 个节点的情绪值为 $a_i$，其中 $a_i$ 是一个整数，可能为正，也可能为负。

为了改善整体情绪氛围，小蓝购买了一种名为“情绪放大器”的工具。该工具允许他选择一段至少包含一个用户节点的连续区间，并将这个区间内所有用户节点的情绪值都乘以一个整数 $k$。只是，工具启动成本高昂，小蓝只能使用它一次。

现在，请你帮助小蓝计算，在经过这样一次操作后（一定要操作），所有用户节点的情绪值之和最大会是多少。

输入格式

第一行包含两个整数 $n$ 和 $k$，分别表示情绪链路的长度和放大器的倍数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示每个用户节点的情绪值。

输出格式

输出一行，包含一个整数，表示经过一次操作后，所有用户节点情绪值之和的最大可能值。

5 2
-1 2 -3 4 -5

1

提示

【样例说明】

最优的做法是选择区间 $[4]$ 并使用工具。使用后这 $n$ 个用户节点的情绪值依次为 $[-1, 2, -3, 8, -5]$，总和为 $1$。

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$2 \leq n \leq 10^3$，$1 \leq k \leq 10^3$，$-10^3 \leq a_i \leq 10^3$。

对于 $100\%$ 的评测用例，$2 \leq n \leq 10^5$，$1 \leq k \leq 10^5$，$-10^5 \leq a_i \leq 10^5$。