Problem1643--值钱的木头

1643: 值钱的木头

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit

Description

现有一堆值钱的木头,它们排成一行,河神给了你一个可以改变一个区间内的木头的价值的机会(注意这个区间不能越过边界),因为这是河神给你的选择,因此你必须要把握这次机会,也就是说你必须改变一个区间内木头的价值。
当然你的目的是让这堆木头的总价值最高。

Input

第一行输入一个T(T <= 5),表示测试数据总数。
接下来2*T行,每组数据有2行。
每组数据第一行首先输入一个n(n <= 100000),接下来输入n个整数,分别表示这些木头的价值(-1000<=木头价值<=1000)
每组数据第二行输入两个整数x,y,其中x表示可以改变的区间的大小,y表示你可以把这个区间内的木头价值变为y(1<= x <= n,-1000<=y<=1000)

Output

你需要输出你所能获得的最大价值(这个价值可能为负数,表明你可能被河神给坑了)

Sample Input Copy

1
5
2 -5 -5 23 -11
1 3

Sample Output Copy

18

HINT

显然你只需要把-11改为3就可以得到最大价值18。

Source/Category