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.
输入解释
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)$
输出解释
For each test case, output one line "Case #x: y", where x is the case number (starting from 1) and y is the answer.