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

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

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

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

미리 작성된 코드

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

#include <stdio.h>

int n, W;
int w[101];
int v[101];
int dt[101][10001];

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

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

    printf("%d", f(n, W));
    return 0;
}

제출할 때는 완성한 f 함수의 정의 전체만 제출한다. 헤더, 전역 변수와 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\)이다.