3249. 限量供应

单点时限: 4.0 sec

内存限制: 256 MB

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

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

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

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

  2. 在不违背 1 的前提下,吃的所有菜的卡路里总和应尽可能小。

输入格式

第一行是一个整数 ,表示测试数据组数。

接下来是 组测试数据,每组数据两行。

第一行四个整数 。其中 表示菜的种数,其余变量含义如题中描述。

第二行 个整数:

输出格式

对于每组数据,输出 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

7 人解决,9 人已尝试。

16 份提交通过,共有 55 份提交。

6.6 EMB 奖励。

创建: 2 年,8 月前.

修改: 2 年,4 月前.

最后提交: 2 年,4 月前.

来源: 2017 华东师范大学校赛

题目标签