최대 \(W\)만큼의 무게를 담을 수 있는 배낭이 있다.

배낭에 넣을 수 있는 \(N\)개의 물건이 주어지며, 각 물건은 무게와 가치를 가지고 있다.

각 물건은 최대 한 번만 선택할 수 있다. 선택한 물건들의 무게 합은 \(W\)를 초과할 수 없다.

물건을 적절히 선택하여 배낭에 담은 물건들의 가치 합의 최댓값을 Bottom-up 방식으로 구하시오.

미리 작성된 코드

아래 코드에서 주석으로 표시된 부분에 코드를 작성한다.

#include <stdio.h>

int w[101];
int v[101];
int dt[101][10001];

int main() {
    int n, W;

    scanf("%d %d", &n, &W);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &w[i], &v[i]);
    }

    /* 코드를 작성하세요. */

    printf("%d", dt[n][W]);
}

제출할 때는 입력 이후에 들어갈 Bottom-up 계산 코드만 제출한다. 헤더, 전역 배열, main 함수의 시작 부분, 입력 코드, 출력 코드와 마지막 닫는 중괄호는 제출하지 않는다.

입력

첫째 줄에 물건의 개수 \(N\)과 배낭이 담을 수 있는 최대 무게 \(W\)가 공백으로 구분되어 주어진다.

둘째 줄부터 \(N\)개의 줄에 걸쳐 각 물건의 무게와 가치가 한 줄에 하나씩 공백으로 구분되어 주어진다.

출력

첫째 줄에 무게 합이 \(W\)를 초과하지 않도록 물건을 선택했을 때 얻을 수 있는 가치 합의 최댓값을 출력한다.

제한 사항

• \(1 \le N \le 100\)
• \(1 \le W \le 10,000\)
• 각 물건의 무게와 가치는 \(1\) 이상 \(100\) 이하이다.

예제 입력 1

4 5
2 3
1 2
3 3
2 2

예제 출력 1

7

예제 설명 1

첫 번째, 두 번째, 네 번째 물건을 선택하면 무게 합은 \(5\)이고 가치 합은 \(7\)이다.