E. 限量供应 - 「游族杯」上海市高校程序设计邀请赛暨华东师范大学第九届 ECNU Coder 程序设计竞赛 (专业组)

仪表盘所有提交榜单

单点时限: 4.0 sec

内存限制: 256 MB

华东师大的食堂常常有许多很奇怪的菜，比方说：玉米炒葡萄、玉米炒草莓、玉米炒香蕉……所以很多同学，包括你，去食堂吃东西，是只吃菜，不吃饭的。

但这些菜都是限量供应的：如果你今天点了某一道菜，那么接下来 $r$ 天（不包括今天）你都不能再点这道菜了。当然，同一道菜在同一天内点两份也是不可以的。此外，因为你是从来不吃饭的，所以为了保证能量充足，你每天吃的所有菜的卡路里总和必须大于等于 $C$ 。

在本学期的 $m$ 天中，你每天都要在食堂吃。你现在既想吃得多，又不能吃得太多，所以你提出了以下两个要求：

第一行是一个整数 $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}, \dots, 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

NaN

比赛状态发生变化，点 OK 刷新。

OK

「游族杯」上海市高校程序设计邀请赛暨华东师范大学第九届 ECNU Coder 程序设计竞赛 (专业组)