有 $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\%):$ 无特殊限制。