책장 2

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$입니다.