Problem Description

Neko has a loop of size $n$.
The loop has a happy value $a_{i}$ on the $i-th(0 \leq i \leq n - 1)$ grid.
Neko likes to jump on the loop.She can start at anywhere. If she stands at $i-th$ grid, she will get $a_{i}$ happy value, and she can spend one unit energy to go to $((i + k) \bmod n)-th$ grid. If she has already visited this grid, she can get happy value again. Neko can choose jump to next grid if she has energy or end at anywhere.
Neko has $m$ unit energies and she wants to achieve at least $s$ happy value.
How much happy value does she need at least before she jumps so that she can get at least $s$ happy value? Please note that the happy value which neko has is a non-negative number initially, but it can become negative number when jumping.

Input

The first line contains only one integer $T ( T \leq 50)$, which indicates the number of test cases.
For each test case, the first line contains four integers $n, s, m, k(1 \leq n \leq 10^4, 1 \leq s \leq 10^{18}, 1 \leq m \leq 10^9, 1 \leq k \leq n)$.
The next line contains $n$ integers, the $i-th$ integer is $a_{i-1}(-10^9 \leq a_{i-1} \leq 10^9)$

Output

For each test case, output one line "Case #x: y", where x is the case number (starting from 1) and y is the answer.

2
3 10 5 2
3 2 1
5 20 6 3
2 3 2 1 5

Case #1: 0
Case #2: 2