对于给定的由 个整数组成的数组 ，小龙和小蛇借助于此数组进行游戏。 游戏步骤如下： 小龙选择一个非空区间 ； 小蛇选择一个非空区间 ； 将选中的区间中的全部元素均乘上 ，得到数组 ； 游戏只进行一轮，三个步骤结束后立即停止。 小龙想要让数组 的元素之和尽可能大，小蛇想要让数组 的元素之和尽可能小。假设双方都采取的是最优策略，请你计算操作后得到的数组 的元素之和。 请注意，区间 和 可以相交，但只结算一次，即若某一个位置被小龙和小蛇同时选中，依旧只乘一次。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：第一行输入两个整数 代表数组中的元素数量、乘数。第二行输入 个整数 代表数组元素。除此之外，保证单个测试文件的 之和不超过 。

输出描述:

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