3010. Coins (III)

单点时限: 1.0 sec

内存限制: 256 MB

In a strange shop there are $n$ types of coins of value $A_1, A_2, \ldots, A_n$. $C_1, C_2, \ldots, C_n$ denote the number of coins of value $A_1, A_2, \ldots, A_n$ 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$ ($T \le 10$), denoting the number of test cases.

Each case starts with a line containing two integers $n$ ($1 \le n \le 100$) and $m$ ($1 \le K \le 100~000$). The next line contains $2n$ integers, denoting $A_1, A_2, \ldots, A_n, C_1, C_2, \ldots, C_n$ ($1 \le A_i \le 100~000, 1 \le C_i \le 1~000$). All $A_i$ 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 年,1 月前.

修改: 6 年,12 月前.

最后提交: 10 月,1 周前.

来源: Coins 系列

题目标签
DP