Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Burger King

By hasan169 · Limits 1s, 512 MB

Every day, more than 11 million guests visit BURGER KING® restaurants around the world. And they do so because our restaurants are known for serving high-quality, great-tasting, and affordable food. Founded in 1954, BURGER KING® is the second largest fast food hamburger chain in the world.

Recently, they launched a branch in Banani, Dhaka and Mr. Panda is really excited about it. He wants to treat his girlfriend at Burger King. He has some fixed budget. As there are several items, he wants find out how many ways he can give her a treat with different items with his fixed budget.

Either he will spend all of his money for buying K items among all N items using budget B, or he will not go to that restaurant. Mr. Panda has some special offer from his credit card company, so some items may even cost negative. It isn’t realistic, but neither is a person named Mr. Panda visiting Burger King.

Input

The first line of input gives contains an integer T (1 ≤ T ≤ 100), the number of test cases. T test cases follow.

For each test case the first line will contain the value N (1 ≤ N ≤ 100), the number of items in the restaurants. The next line will contain the value K (1 ≤ K ≤ 3), the number of items he needs to pick. The line after that will contain the value B (1 ≤ B ≤ 10000), the amount of budget he must spent. And, finally the last line will contain a space separated list of N integers. Each integer X (|X| ≤ 100) indicates the price of an item in the restaurant.

Output

For each test case, output one line containing “Case t: ” followed by the number of ways you can buy K items using the budget.

Sample

InputOutput
3
5
2
7
1 -1 8 1 6
5
3
10
2 3 5 7 1
3
1
4
1 2 3
Case 1: 3
Case 2: 2
Case 3: 0

In the first sample test case, Mr. Panda has to buy two items from Burger King using 7 Taka. He can the buy items in the following 3 ways:

  • Items 1 and 5 (Total: 7 Taka)
  • Items 2 and 3 (Total: 7 Taka)
  • Items 4 and 5 (Total: 7 Taka)

Discussion

Statistics


88% Solution Ratio

oneoff.PYhhII1D3GEarliest, Dec '16

bhowmickFastest, 0.0s

MuntasirAK47Lightest, 0 B

mdvirusShortest, 297B

Submit

Login to submit