도둑의 딜레마

실행 시간 제한	메모리 제한
3 초	512 MB

📃 해결할 문제

도둑은 한 가방에 최대한 많은 가치의 물건을 넣고자 합니다.

하지만 도둑의 가방에는 찢어짐을 방지하기 위해 들어갈 수 있는 무게의 제한이 있습니다.

각 물건은 무게와 가치를 가지고 있으며, 도둑은 물건을 통째로 가져갈지 아니면 아예 가져가지 않을지 결정해야 합니다.

도둑이 가져갈 수 있는 물건들의 조합 중 가치의 합을 최대화하기 위해 넣을 수 있는 물건들을 찾는 프로그램을 작성하세요.

💻 입력

입출력 데이터는 다음 순서대로 각 줄마다 값이 입력됩니다.

W: 가방의 용량을 나타내는 정수 (1 이상 10000 이하)
weights: 물건의 무게를 나타내는 정수 배열 (1 이상 1000 이하의 길이, 각 원소는 1 이상 10000 이하)
values: 물건의 가치를 나타내는 정수 배열 (weights와 동일한 길이, 각 원소는 1 이상 10000 이하)

🖨️ 출력

도둑이 가져갈 수 있는 물건들의 가치의 최대값을 출력하세요.

💻 예제 입력 1

7
1 3 4 5
1 4 5 7

🖨️ 예제 출력 1

💻 예제 입력 2

10
2 3 4 5
3 4 5 6

🖨️ 예제 출력 2

💻 예제 입력 3

500
4 7 5 1 1 3 3 4 8 5 1 8 9 2 9 1 4 4 2 2 1 7 8 8 7 6 2 2 9 8 5 2 5 1 7 7 5 2 6 4 3 6 3 4 5 9 9 9 9 3 5 8 7 8 2 5 1 2 7 2 5 8 6 9 5 6 4 2 9 1 1 7 2 6 1 6 4 4 6 8 4 8 4 2 8 9 2 1 2 5 3 1 9 3 9 7 4 4 4 6
2 5 3 4 4 8 5 7 1 9 8 2 4 5 8 2 4 6 5 4 6 6 4 3 8 4 4 2 8 8 8 4 6 2 4 2 5 4 6 2 8 5 1 1 9 8 8 7 7 3 9 1 2 9 7 1 1 4 2 9 3 9 3 2 5 7 8 9 5 7 8 9 1 5 2 8 8 3 3 4 2 7 4 8 4 3 7 2 9 2 5 1 3 5 1 8 5 5 6 7