126. 连续子数组最大和

内存限制：256 MB 时间限制：1.000 S
提交提交记录统计露一手!

题目描述

小红拿到了一个数组，她希望进行最多一次操作：将一个元素修改为x。小红想知道，最终的连续子数组最大和最大是多少？

输入

第一行输入一个正整数t，代表询问次数。 

对于每次询问，输入两行： 

第一行输入两个正整数n和x。代表数组的大小，以及小红可以修改成的元素。 

第二行输入n个正整数a_i，代表小红拿到的数组

输出

输出 t 行，每行输出一个整数，代表连续子数组的最大和。

样例输入 复制 

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

样例输出 复制 

15
-2
15

提示

例如输入：

6 10

4 -2 -11 -1 4 -1

可以用10 替换 -11，连续子数组的最大和：4 -2 10 -1 4，总和为：15

数据范围： 

1 ≤ t ≤ 100000 

1 ≤ n ≤ 200000 

-10^9 ≤ x ,a_i  ≤ 10^9 

每组所有询问的n的和不超过200000。