서투른 배낭 채우기

시간 제한6초메모리 제한512 MB

요약

n개의 물체와 용량 c가 주어질 때, 남은 물체를 더 넣으면 c를 넘게 되는 부분집합의 최소 무게 합을 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 그리디, 정렬, 이분 탐색
정답자: 아직 제출이 없습니다

문제

우리에게 정수 용량의 배낭 하나와 정수 크기의 물건 여러 개가 있다. 배낭을 가득 채우려고 하지만, 우리는 이것을 정말 못해서 남은 물건 중 어느 것으로도 더 채울 수 없는 공간을 많이 낭비하고 만다. 아니, 우리는 이 일을 최적으로 못한다! 우리는 도대체 얼마나 못할 수 있을까?

남은 물건 중 어느 것도 배낭에 넣을 수 없게 되는, 사용할 수 있는 용량의 최솟값을 구하라. 예를 들어 무게가 $3$ , $5$ , $3$ 인 물건 $3$ 개가 있고 배낭의 용량이 $6$ 이라고 하자. 무게 $5$ 인 물건을 어리석게도 먼저 넣으면, 나머지 두 물건 중 어느 것도 배낭에 넣을 수 없다. 이것이 우리가 할 수 있는 최선의 실패이므로 답은 $5$ 이다.

입력

첫째 줄에 정수 $n$ ( $1 \le n \le 1,000$ )과 $c$ ( $1 \le c \le 10^5$ )가 주어진다. $n$ 은 넣으려는 물건의 수이고 $c$ 는 배낭의 용량이다.

다음 $n$ 개의 줄에 각각 정수 $w$ ( $1 \le w \le c$ )가 하나씩 주어진다. 이것은 물건의 무게이다.

출력

남은 물건 중 어느 것도 배낭에 넣을 수 없게 되는, 사용할 수 있는 용량의 최솟값을 정수 하나로 출력한다.

예제1

예제 1
입력
```
3 6
3
5
3
```
예상 출력
```
5
```