题目描述
小明有一个容量为 V 的背包。

这天他去商场购物，商场一共有N 件物品，第 i 件物品的体积为 wi，价值为 vi。

小明想知道在购买的物品总体积不超过 V的情况下所能获得的最大价值为多少，请你帮他算算。

输入描述
输入第 11 行包含两个正整数 N,V，表示商场物品的数量和小明的背包容量。

第 2∼N+1 行包含 2 个正整数 w,v，表示物品的体积和价值。

1≤N≤100 ,1≤V≤1000,≤wi,vi≤10000。

输出描述
输出一行整数表示小明所能获得的最大价值。

样例

输入

5 20
1 6
2 5
3 8
5 15
3 3 

输出

37

代码示例

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int n = scan.nextInt();
        int m = scan.nextInt();
        int[] w = new int[m+1];
        int[] v = new int[n+1];
        for(int i = 1;i<=n;i++){
            v[i] = scan.nextInt();
            w[i] = scan.nextInt();
        }
        int[][] dp = new int[n+1][m+1];
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=m;j++){
                if(j>=v[i]){
                    dp[i][j] = Math.max(dp[i][j-v[i]]+w[i],dp[i-1][j]);
                }else{
                  dp[i][j] = dp[i-1][j];
                }
            }
        }
        System.out.println(dp[n][m]);
        scan.close();
    }
}