Problem 1086 --撸猫大师

1086: 撸猫大师

Time Limit: 1 Sec  Memory Limit: 32 MB
Submit: 75  Solved: 13
[Submit][Status][Web Board][Creator:]

Description

撸猫一时爽,一直撸猫一直爽。撸猫,也就是对猫进行爱抚的行为,是现代人热衷的爱好之一。铲屎官们用撸体现着对猫主子的爱,尤其是在自己忙碌一天休息的时候撸个猫解个乏,似乎已经成为最理想的生活状态。

卷心菜就是一名撸猫成瘾患者,他在家里养了很多只猫主子,每天下班后,就可以尽情享受撸猫的快乐时光。同时猫主子也很享受被撸的过程,每只猫的快乐值上限为w,卷心菜每次可以撸一只猫,被撸的这只猫快乐值就会增加x。但由于其他猫会产生嫉妒心理,除了被撸的猫以外,其他所有猫快乐值都会减少y。当某只猫的快乐值降低到0或者快乐值超过上限w时,这只猫就会带领其它猫一起离家出走,这时所有猫的快乐值都会降为0,且不能再被撸。

卷心菜是一名撸猫大师,因此,他能够通过合理的撸猫方式使所有猫的快乐值之和最大,但卷心菜想知道最大的快乐值之和是多少,请你写个程序帮帮他。


Input

多组测试用例

第一行一个整数T,代表测试用例组数。

对于每组测试用例

第一行有四个整数 n,x,y,w。n代表猫的数量,x,y,w与题目中所述一致。

第二行有n个整数a1,a2,...,an,代表这n只猫的初始快乐值。


数据规模 0<T<=50; 0<n<=10000; 0<=x,y<=50; 0<ai<=w<=500;

数据保证T组测试用例中n的和不超过250000,且超过75%的测试用例使用随机数据


Output

对于每组测试用例,在一行中输出一个整数,代表最大快乐值之和。

Sample Input

3
2 5 2 50
33 20 
3 20 7 500
2 6 7
5 30 5 50
30 30 30 30 30

Sample Output

95
15
150

HINT

Source

[Submit][Status]