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

E. 限量供应

单点时限: 4.0 sec

内存限制: 256 MB

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

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

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

  1. 在不违背上述条件的前提下,吃的菜的数目(不是种类数)应尽可能多;

  2. 在不违背 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