| 배낭 문제 |
|---|
스티브는 학교에서 사제동행으로 여행을 가기로 하였다. 스티브가 준비한 배낭에는 정해진 부피만큼 물건을 담을 수 있다. 될 수 있으면 많은 물건을 넣고 싶지만 그럴 수 없다는 것을 알게 된 스티브는 자신이 좋아하는 물건들을 넣어 최고의 만족도가 나올 수 있도록 배낭을 꾸리기로 결심하였다. 배낭의 물건들은 각각의 부피와 만족도를 지니고 있다. 배낭의 부피가 정해져 있기 때문에 물건을 선택하여 배낭에 넣을 때, 부피를 고려해야 한다. 스티브의 만족도가 최상이 될 수 있도록 하는 프로그램을 작성하시오. |
| 입력 | |
|---|---|
첫째 줄에는 물건의 갯수 \(N(1 \leq N \leq 1000)\)과 배낭의 용량 \(W (1 \leq W \leq 1000)\)이 주어진다. 둘째 줄부터 \(N+1\)번째 줄까지 물건들의 부피 \(V(1 \leq V \leq 1000)\)와 만족도 \(S(1 \leq S \leq 1000)\)이 한 줄에 하나씩 입력된다. | |
| 출력 | |
|---|---|
배낭의 부피를 초과하지 않으면서 선택한 물건들의 만족도 총합의 최대값을 출력한다. | |
| 예시 | |||
|---|---|---|---|
| 1 | 입력 | 6 17 4 7 2 10 6 6 4 7 2 5 10 4 | |
| 출력 | 30 | ||