농부 창호는 최근에 소 도서관을 위해 새로운 책장을 구입했는데, 책들이 워낙 빠른 속도로 채워져서 이제 남은 것은 가장 위에 있는 공간뿐이다.

창호은 N(1≤N≤20)마리의 소를 데리고 있고, 각각의 소의 키는 H_i (1≤H_i≤100만)이다. 책장의 높이는 B이다(1≤B≤S). 여기서 S는 모든 소들의 키의 합을 의미한다.

책장의 꼭대기에 닿기 위해서, 한 마리 이상의 소가 아래에 있는 소를 밟고 올라서게 된다. 이 때 소들의 총 높이는 각 소들의 키의 합이다. 꼭대기에 닿으려면 총 높이가 최소한 책장의 높이만큼은 되어야 한다.

소들이 필요 이상으로 높이 올라가면 위험할 수 있기 때문에, 창호는 소들이 책장에 가까스로 닿을 수 있는 소들의 부분집합을 찾으려고 한다. 소들이 책장의 높이 이상으로 올라서면서 책장과의 높이 차이가 최소가 되도록 하자.

책 꺼내기 Part2 timer 1s memory - MB

책 꺼내기 Part2 1s - MB