小红拿到了一个数组，她希望进行最多一次操作：将一个元素修改为x。小红想知道，最终的连续子数组最大和最大是多少？
输入描述
第一行输入一个正整数t，代表询问次数。 对于每次询问，输入两行： 第一行输入两个整数n和x。代表数组的大小，以及小红可以修改成的元素。 第二行输入n个正整数a_i，代表小红每次询问拿到的数组。 1 ≤ t ≤ 100000 1 ≤ n ≤ 200000 -10^9 ≤ x, a_i ≤ 10^9 每组所有询问的n的和不超过200000。
输出描述
输出t行，每行输出一个整数，代表每次询问能够得到的连续子数组的最大和。
示例
示例 1
输入
3 5 10 5 -1 -5 -3 2 2 -3 -5 -2 6 10 4 -2 -11 -1 4 -1
输出
15 -2 15
时间限制 1000 ms · 内存限制 128 MB