Migrated from Lutece 600 数的划分

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给定$N$个数，把他们划分成最少的部分，使得每部分之和小于某个定值$M$。

Input

输入由不超过$100$组输入数据组成。

每组数据由给出$N$和$M$的一行开始。$N$不超过$18$，$M$不超过$1000000000$。

接下里$N$行每行一个数，每个数不超过$M$。

Output

对于每组数据，先输出Case T: ，其中$T$是数据的编号（从$1$开始）。

然后输出把这$N$个数划分成的最少部分。

Samples

1
3 3
1 3 2

Case 1: 2

Resources

UESTC Training for Dynamic Programming