주사위 집어 들기

시간 제한1초메모리 제한1024 MB

요약

주사위 K개와 첫 번째 눈이 주어질 때, 목표 합 T에 도달할 확률을 가장 높이는 재굴림 개수를 구합니다. 확률이 같으면 가장 작은 개수를 출력합니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 확률, 조합론
정답자: 아직 제출이 없습니다

문제

두 명의 플레이어가 $K$ 개의 6면 주사위로 게임을 합니다. 한 명이 $K\ldots 6K$ 범위의 수를 부르면, 다른 플레이어는 그 수가 나오도록 주사위를 굴립니다. 첫 번째 굴림이 끝나면, 플레이어는 원하는 개수( $0\ldots K$ )만큼 주사위를 집어 들어 다시 굴릴 수 있습니다.

주사위 개수, 목표 수, 그리고 첫 번째 굴림에서 나온 수들이 주어졌을 때, 두 번째 굴림에서 목표 수를 얻을 확률을 가장 높이려면 몇 개의 주사위를 집어 들어야 합니까?

입력

첫 줄에 두 정수 $K$ (주사위 개수)와 $T$ (목표 수)가 주어집니다. $2 \leq K \leq 24$ , $K \leq T \leq 6K$ 입니다.

다음 줄에는 첫 번째 굴림에서 각 주사위가 보인 수 $K$ 개가 주어집니다. 모든 값은 $1$ 부터 $6$ 까지의 정수입니다.

출력

합이 $T$ 가 될 확률을 가장 높이려면 다시 굴려야 할 주사위 개수를 한 정수로 출력합니다. 어떤 주사위를 집어 들지는 플레이어가 고를 수 있지만, 출력은 개수만 묻습니다.

같은 최대 확률을 주는 개수가 여럿이면 가장 작은 값을 출력합니다.

예제4

예제 1
입력
```
3 9
5 4 1
```
예상 출력
```
1
```
예제 2
입력
```
4 13
2 2 2 2
```
예상 출력
```
3
```

예제 3

입력

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

예상 출력

예제 4
입력
```
6 21
1 2 3 4 5 6
```
예상 출력
```
0
```