B. Gold Medal
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

What a busy week! This weekend, $$$n$$$ programming contests will be held at the same time.

Each contest will award one gold medal for every $$$k$$$ participating teams. That is to say, if there are $$$t$$$ teams participating in the contest, $$$\lfloor \frac{t}{k} \rfloor$$$ gold medals will be awarded, where $$$\lfloor x \rfloor$$$ is the largest integer not exceeding $$$x$$$. Currently, there will be $$$a_i$$$ teams participating in the $$$i$$$-th contest.

BaoBao is the coach of a university with $$$m$$$ teams, and he hasn't decided which contests these teams should participate in. Please help him assign each team to a contest, so that the total number of gold medals handed out by all contests is maximized.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 100$$$) indicating the number of test cases. For each test case:

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 100$$$, $$$1 \le k \le 10^9$$$), indicating the number of contests and the ratio of gold medals.

The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the current number of teams participating in the $$$i$$$-th contest.

The third line contains an integer $$$m$$$ ($$$1 \le m \le 10^9$$$), indicating the number of teams you need to assign a contest to.

Output

For each test case output one line containing one integer indicating the maximum total number of gold medals handed out by all contests.

Example
Input
2
3 10
239 141 526
6
2 1
300 100
1000
Output
91
1400
Note

For the first sample test case, send $$$2$$$ teams to the $$$1$$$-st contest and $$$4$$$ teams to the $$$3$$$-rd contest. The total number of gold medals will be $$$\lfloor \frac{239 + 2}{10} \rfloor + \lfloor \frac{141 + 0}{10} \rfloor + \lfloor \frac{526 + 4}{10} \rfloor = 24 + 14 + 53 = 91$$$.