Picking Up the Dice

Time limit1sMemory limit1024 MB

Summary

Given K dice and a first roll, find the smallest number of dice to re-roll that maximizes the chance of reaching the target total T.

Level: Medium6 of 10
Topics: Dynamic programming, Probability, Combinatorics
Solved: No attempts yet

Statement

Two players play a game with a set of $K$ six-sided dice. One player calls out a number in the range $K\ldots 6K$ , and the other player tries to roll that number. After the first roll, the player may pick up any number of dice ( $0\ldots K$ ) and roll them again.

Given the number of dice, the target number, and the numbers the player rolled the first time, how many dice should the player pick up to maximize the chance of getting the target number on the second roll?

Input

The first line contains two integers, $K$ , the number of dice, and $T$ , the target number. $2 \leq K \leq 24$ , $K \leq T \leq 6K$ .

The next line contains $K$ integers, the numbers shown on each die in the first roll. Every value is an integer from $1$ to $6$ .

Output

Print a single integer, the number of dice the player should pick up and roll again to maximize the chance of getting a total of $T$ . The player chooses which dice to pick up, but the output asks only for the count.

If more than one count gives the same maximum probability, print the smallest one.

Examples4

Example 1
Input
```
3 9
5 4 1
```
Expected output
```
1
```
Example 2
Input
```
4 13
2 2 2 2
```
Expected output
```
3
```

Example 3

Input

18 90
1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6

Expected output

Example 4
Input
```
6 21
1 2 3 4 5 6
```
Expected output
```
0
```