Server Time: Tue Jul 17, 2018 5:26 am
Welcome ( logout
1233 - Coin Change (III)
  PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 32 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

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

Each case starts with a line containing two integers n (1 ≤ n ≤ 100), m (0 ≤ m ≤ 105). The next line contains 2n integers, denoting A1, A2 ... An, C1, C2 ... Cn (1 ≤ Ai ≤ 105, 1 ≤ Ci ≤ 1000). All Ai will be distinct.

Output

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

Sample Input

Output for Sample Input

2

3 10

1 2 4 2 1 1

2 5

1 4 2 1

Case 1: 8

Case 2: 4

 


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan