1313_憨豆先生卖豆子

憨豆先生卖扁豆。他的仓库里有n袋豆子，分别用 1, 2, 3, ..., n 编号。第i袋有 w_i 公斤豆子。为了方便零售，憨豆先生改用小包装，把豆子分装成一个个小袋出售。分装的方式是这样的：

假设每小袋的重量是p公斤。首先，他从仓库取出若干袋编号连续的豆子（至少一袋），然后把这些豆子全部倒在一张大桌子上。每次称出p公斤，装入一个小袋中。直到桌子上剩下少于p公斤豆子。这些剩下的豆子就留给憨豆先生自己和他的宝贝熊做晚餐了。

当然，为了保持身材苗条，憨豆先生不希望晚餐吃太多豆子了，因此他希望桌上最后剩下的豆子不超过k公斤。而且，他希望制作尽可能多的小包装豆子用于出售。请问，在不违背以上条件的情况下，憨豆先生最多能制作多少个小包装用于出售？

输入的第一行是一个整数T ，表示测试用例的个数。

每个测试用例有两行。第一行有3个整数，n , p , k ，它们的意思如上所述。 0 < n, p < 1000001 , 0 ≤ k < p

第二行有n个整数 w₁, w₂, ... , w_n 。第i个整数表示第i袋豆子的重量。 0 ≤ w_i < 32768 。数字之间用空格分隔。

为每个测试用例输出一行 :

Case X: Y

其中X表示第几个测试用例（从1开始），Y表示最多可以制作出的小包装数。

如果想尽所有办法都无法避免晚餐要吃超过k公斤的豆子，Y就取值-1。

3
10 20 10
0 3 1 8 19 39 2 9 1 8
3 100 10
32 34 23
1 5 3
1

Case 1: 4
Case 2: -1
Case 3: 0