정올이는 최근 도서관을 위해 또 다른 책장을 구입했지만, 책장이 빨리 가득 차서 이제 사용할 수 있는 공간은 맨 위뿐입니다.

정올이네 도서관은 각각 키가 H_i (1 <= H_i <= 1,000,000)인 N (1 <= N <= 20) 명의 고객들이 이용합니다. 책장의 높이는 B (1 <= B <= S, 여기서 S는 모든 고객의 키의 합)입니다.

책장의 맨 위에 도달하려면 한 명 이상의 고객이 서로의 머리 위에 서서 그들의 키의 합이 책장의 높이 이상이어야 고객들이 꼭대기에 도달할 수 있습니다.

필요 이상으로 높은 고객들의 스택은 위험할 수 있기 때문에, 여러분의 임무는 책장에 도달할 수 있는 가장 작은 높이를 갖는 고객들의 집합을 찾는 것입니다.

고객들의 최적의 스택과 책장 사이의 최소 '초과' 높이를 출력하는 프로그램을 작성하시오.

책장2 timer 1s memory 1024MB

책장2 1s 1024MB