책장 2

면접 대비

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

요약

소 20마리의 키와 책장 높이 B가 주어질 때, B 이상이 되는 부분집합 합의 최솟값에서 B를 뺀 값을 구한다.

난이도: 보통10점 중 4점
유형: 완전 탐색, 비트 연산, 배열, 그리디
정답자: 아직 제출이 없습니다

문제

Farmer John이 소 도서관에 책장을 하나 더 들여놓았지만, 책장은 금세 가득 차서 이제 남은 공간은 맨 위쪽뿐입니다.

FJ에게는 소가 $N$ 마리 있고 ( $1 \le N \le 20$ ), 소 $i$ 의 키는 $H_i$ 입니다 ( $1 \le H_i \le 1{,}000{,}000$ — 아주 키가 큰 소들입니다). 책장의 높이는 $B$ 이며, $1 \le B \le S$ 입니다. 여기서 $S$ 는 모든 소의 키의 합입니다.

책장 맨 위에 닿으려면 한 마리 이상의 소가 서로의 위에 올라가 하나의 탑을 쌓을 수 있으며, 이때 탑의 전체 높이는 그 탑에 포함된 소들의 키의 합과 같습니다. 소들이 맨 위에 닿으려면 이 전체 높이가 $B$ 이상이어야 합니다.

필요 이상으로 높은 탑은 위험하므로, 책장에 닿으면서도 가능한 한 낮은 탑을 이루는 소들의 집합을 찾으세요. 이 최적의 탑의 높이와 책장 높이의 차이, 즉 최소 '초과' 높이를 출력하세요.

입력

첫째 줄: 공백으로 구분된 두 정수 $N$ 과 $B$ .
둘째 줄부터 $N+1$ 째 줄까지: $i+1$ 째 줄에는 정수 $H_i$ 가 하나 주어집니다.

출력

정수 하나: 최적의 소 집합의 전체 높이와 책장 높이의 (음이 아닌) 차이.

참고

예를 들어 1, 3, 4, 5번 소를 사용하면 전체 높이가 $3 + 3 + 5 + 6 = 17$ 이 됩니다. 전체 높이를 정확히 16으로 만드는 것은 불가능하므로, 답은 $17 - 16 = 1$ 입니다.

예제4

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