题目描述

你有一个魔法项链，现在你想要强化一下这件装备。你可以将魔法项链看做一条从头到尾串有 $n$ 个不同魔力值宝石的绳子。根据你目前的冒险等级，你可以仅将其中的一颗宝石的魔力值强化并改变为 $v$ 。

魔法项链的攻击力等于任意连续的几个宝石的魔力值之和的最大值。给定的项链与相应的冒险等级强化能力，请你计算强化后魔法项链的最大攻击力是多少?

输入描述

第一行输入一个正整数$t$，代表魔法项链个数。 每个项链对应输入两行: 第一行输入两个正整数$n$和$v$。代表项链的长度（即宝石个数），以及你可以修改成的魔力值大小。

第二行输入$n$个正整数$a_i$，代表项链上每个宝石的魔力值大小。

$1 \leq t \leq 100000$

$1 \leq n \leq 200000$

$-10^9 \leq v,a_1 \leq 10^9$

每组所有项链的$n$的和不超过$200000$。

输出描述

输出t行，每行输出一个整数，代表强化后魔法项链的最大攻击力。

样例

输入

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

输出

15
-2
15

提示

第一组询问，强化第二个宝石。

第二组询问，不进行任何强化。

第三组询问，强化第三个宝石。