7 人解决，10 人已尝试。
16 份提交通过，共有 57 份提交。
6.8 EMB 奖励。
3249. 限量供应
单点时限: 4.0 sec
内存限制: 256 MB
华东师大的食堂常常有许多很奇怪的菜，比方说：玉米炒葡萄、玉米炒草莓、玉米炒香蕉……所以很多同学，包括你，去食堂吃东西，是只吃菜，不吃饭的。
但这些菜都是限量供应的：如果你今天点了某一道菜，那么接下来 $r$ 天（不包括今天）你都不能再点这道菜了。当然，同一道菜在同一天内点两份也是不可以的。此外，因为你是从来不吃饭的，所以为了保证能量充足，你每天吃的所有菜的卡路里总和必须大于等于 $C$。
在本学期的 $m$ 天中，你每天都要在食堂吃。你现在既想吃得多，又不能吃得太多，所以你提出了以下两个要求：
-
在不违背上述条件的前提下，吃的菜的数目（不是种类数）应尽可能多；
-
在不违背 1 的前提下，吃的所有菜的卡路里总和应尽可能小。
输入格式
第一行是一个整数 $T$ $(1 \leq T \leq 100)$，表示测试数据组数。
接下来是 $T$ 组测试数据，每组数据两行。
第一行四个整数 $n, m, r, C$ $(1 \leq n \leq 12, 1 \leq m \leq 1000, 1 \leq r \leq 20, 1 \leq C \leq 10^5)$。其中 $n$ 表示菜的种数，其余变量含义如题中描述。
第二行 $n$ 个整数：$c_1, c_2, \ldots, c_n$ $(1 \leq c_i \leq 10^5)$。
输出格式
对于每组数据，输出 Case x: y z。x 表示从 1 开始的测试数据编号，y 和 z 分别表示菜的数目和卡路里总和。如果没有满足要求的方案，y 和 z 是 0 0。
样例
Input
2 7 9 3 3 3 2 2 2 2 3 3 7 5 3 3 3 2 2 2 2 3 3
Output
Case 1: 18 42 Case 2: 11 25
题目标签