There are $n$ boxes numbered $1$ to $n$, where the $i$-th box initially contains $a_i$ balls.

You can perform the following two types of operations:

• Choose a box and remove one ball from it. The cost is 1.
• Choose $m$ consecutive boxes and remove a total of at most $k$ balls from them. The cost is $c$.

Find the minimum cost required to remove all balls.

Each test case contains $T$ datasets.

Input

The first line contains an integer $T$.

For each dataset:

The first line contains four integers $n, m, k, c$.

The second line contains $n$ integers $a_1, \dots, a_n$.

Output

For each dataset:

A single integer representing the answer.

Examples

Input 1

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 1

7
7
6

Subtasks

For $100\%$ of the data, $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$.

Subtask 1 ($17\%$): $n, a_i \le 100$, $\sum n \le 500$.

Subtask 2 ($21\%$): $\sum n \le 500$.

Subtask 3 ($24\%$): $\sum n \le 5 \times 10^3$.

Subtask 4 ($11\%$): $c = 1$.

Subtask 5 ($27\%$): No additional constraints.