Dart Challenge

Time limit1sMemory limit128 MB

Summary

For each dartboard, count how many distinct total scores k darts can produce, where each dart misses or scores s_i, 2s_i, or 3s_i (no triple on the top area).

Level: Medium4 of 10
Topics: Dynamic programming, Array, Combinatorics, Implementation
Solved: No attempts yet

Problem

Clark and Harry are siblings. As they had been rivals since early childhood, their father decided that each should focus on a different sport once they turned thirteen, so they would not have to compete for success. Now both are twenty and excel in different fields: Clark plays chess, while Harry competes in dart tournaments.

Having won three tournaments in a row, Harry started teasing Clark for not being as successful. Clark retorted that chess is less luck-based and therefore harder. Offended, Harry replied that playing darts optimally requires a great deal of combinatorics. Clark returned an icy smile and remarked that memorizing every possible late-game could hardly be called "combinatorics."

That is how the wager began. Harry bets that he can find all possible late-game scores for generalized dartboards on which memorized late-games are of no help. When Clark showed him a list of possible dartboards, Harry had to admit that he had probably bitten off more than he could chew. As his friend, you have to help him!

A dartboard consists of several areas. Each area has a score assigned for hitting it. Each area also has a double field and a triple field, worth twice and three times the area's score. The only exception is the area with the highest score: it has only a double field and no triple field. Given the scores of the areas, find the number of distinct total scores obtainable with a given number of darts.

A single dart throw scores one of the following:

$0$ if the board is missed
$s_i$ for hitting the single of some area $i$
$2 \cdot s_i$ for hitting the double of some area $i$
$3 \cdot s_i$ for hitting the triple of some area $i$ , except the highest-scoring area

Throwing $k$ darts, the total score is the sum of the individual dart scores (a missed dart adds $0$ ). Count how many distinct totals can be produced.

Input

The first line contains an integer $n$ . Each of the following $n$ lines contains one test case.

Each test case starts with two integers $a$ and $k$ ( $1 \le a \le 100$ , $1 \le k \le 50$ ), the number of areas on the dartboard and the number of darts. Then $a$ integers $s_i$ follow ( $1 \le s_i \le 100$ ), where $s_i$ is the score for hitting area $i$ . All scores are distinct.

Remember that each area has a double field, and every area except the highest-scoring one also has a triple field. It is always possible to score $0$ with any dart by not hitting the board.

Output

For each test case, first output a line of the form Scenario #i:, where $i$ is the scenario number counting from $1$ . On the next line, output the number of distinct total scores obtainable with $k$ darts on the given board. Separate the outputs of different test cases with a single blank line.

Examples1

Example 1

Input

3
21 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 25
2 2 20 10
1 50 1

Expected output

Scenario #1:
172

Scenario #2:
9

Scenario #3:
101