3010. Coins (III)

单点时限: 1.0 sec

内存限制: 256 MB

In a strange shop there are n types of coins of value A1,A2,,An. C1,C2,,Cn denote the number of coins of value A1,A2,,An respectively. You have to find the number of different values (from 1 to m), which can be produced using these coins.

输入格式

Input starts with an integer T (T10), denoting the number of test cases.

Each case starts with a line containing two integers n (1n100) and m (1K100 000). The next line contains 2n integers, denoting A1,A2,,An,C1,C2,,Cn (1Ai100 000,1Ci1 000). All Ai will be distinct.

输出格式

For each case, print the case number and the result.

样例

Input
2
3 10
1 2 4 2 1 1
2 5
1 4 2 1
Output
Case 1: 8
Case 2: 4

39 人解决,47 人已尝试。

57 份提交通过,共有 162 份提交。

4.0 EMB 奖励。

创建: 11 年,8 月前.

修改: 7 年,6 月前.

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

来源: Coins 系列

题目标签
DP