D-乘之_牛客周赛 Round 78

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 对于给定的由 $n$ 个整数组成的数组 $\{a_1,a_2,\dots,a_n\}$ ，小龙和小蛇借助于此数组进行游戏。
$\hspace{15pt}$ 游戏步骤如下：
${\hspace{20pt}}_\texttt{1.}\,$ 小龙选择一个非空区间 $[a, b]$ ；
${\hspace{20pt}}_\texttt{2.}\,$ 小蛇选择一个非空区间 $[c, d]$ ；
${\hspace{20pt}}_\texttt{3.}\,$ 将选中的区间中的全部元素均乘上 $k$ ，得到数组 $a'$ ；
$\hspace{15pt}$ 游戏只进行一轮，三个步骤结束后立即停止。
$\hspace{15pt}$ 小龙想要让数组 $a'$ 的元素之和尽可能大，小蛇想要让数组 $a'$ 的元素之和尽可能小。假设双方都采取的是最优策略，请你计算操作后得到的数组 $a'$ 的元素之和。

$\hspace{15pt}$ 请注意，区间 $[a, b]$ 和 $[c, d]$ 可以相交，但只结算一次，即若某一个位置被小龙和小蛇同时选中，依旧只乘一次。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入两个整数  代表数组中的元素数量、乘数。
第二行输入  个整数  代表数组元素。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，新起一行。输出一个整数，代表操作后数组  的元素之和。

示例1

输入

复制

3
2 4
1 1
6 0
1 1 4 5 1 4
4 -1
-2 1 -10 3

输出

复制

8
0
8

说明

对于第一组测试数据，小龙的最优策略是选择区间 ，一旦这么做了，无论小蛇选择的区间是什么，都不会影响最终答案。
对于第三组测试数据，其中一种最优策略为：龙选择区间 ，小蛇选择区间 。