G. Ahmad and Cinema Syndrome
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ahmad and Monther like watching movies in the cinema, and since they go a lot (they don't), they received a special offer.

They want to watch $$$n$$$ movies, and the ticket of the $$$i$$$-th movie costs $$$a_i$$$ dinars, but they received a special offer where they can pay $$$k$$$ dinars and get $$$m$$$ special tickets that they can use to watch any movie of their liking.

Note that they can buy the offer as many times as they want, and they can have leftover tickets from the special offer at the end.

What is the minimum number of dinars they need to watch all of the movies?

Input

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ – the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ $$$(1 \leq m \leq n \leq 2 \cdot 10^5; 1 \leq k \leq 10^9)$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$.

It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.

Output

For each test case, print the minimum number of dinars you need to spend to watch all movies.

Example
Input
3
4 2 3
1 2 3 4
5 2 4
2 2 2 1 3
6 4 5
4 1 2 3 3 4
Output
6
9
8