有 $n$ 个编号为 $1 \sim n$ 的盒子，初始第 $i$ 个盒子里有 $a_i$ 个球。
你可以进行以下两种操作：
- 选择一个盒子，取走盒子中一个球。消耗代价为 1。
- 选择 m 个编号连续的盒子，从中取出总计不超过 k 个球。消耗代价为 c。
问取走所有球需要消耗的最小代价。
每个测试点中有 $T$ 组数据。
输入格式
第一行，一个整数，表示 $T$。
对于每组数据：
第一行，四个整数，表示 $n,m,k,c$。
第二行，$n$ 个整数，表示 $a_1\dots a_n$。
输出格式
对于每组数据：
一行，一个整数，表示答案。
样例数据
input
3 5 2 4 3 2 2 1 2 2 4 2 4 3 2 4 1 1 10 3 5 1 2 2 2 2 1 1 1 10 2 2
output
7 7 6
子任务
对于 $100\%$ 的数据，$1\le T\le 5\times 10^5,\sum n\le 5\times 10^5,1\le m\le n,1\le c\le k\le 10^9,1\le a_i\le 10^9$。
$\operatorname{Subtask} 1(17\%):n,a_i\le 100,\sum n\le 500$。
$\operatorname{Subtask} 2(21\%):\sum n\le 500$。
$\operatorname{Subtask} 3(24\%):\sum n\le 5\times 10^3$。
$\operatorname{Subtask} 4(11\%):c=1$。
$\operatorname{Subtask} 5(27\%):$ 无特殊限制。