페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#7082

책장2 1초 1024MB

문제

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

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

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

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

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


입력

첫 번째 줄: 공백으로 구분된 두 정수 N과 B가 주어진다.

다음 2줄부터 N+1줄까지: i+1번째 줄에 정수 H_i가 주어진다.


출력

책장의 높이와 최적의 고객 스택의 높이 차이를 나타내는 정수를 출력한다.


예제1

입력
516
3
1
3
5
6
출력
1

여기서는 1번, 3번, 4번, 5번 고객이 모여 총 높이 3 + 3 + 5 + 6 = 17을 얻습니다. 총 높이 16을 얻을 수 없으므로 답은 1입니다.


출처

USACO December 2007 Bronze 2번

역링크