1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner scn = new Scanner(System.in);
        int N=0, M=0;
        N=scn.nextInt();
        M=scn.nextInt();
        int[] need=new int[N+1];
        int[] value = new int[N+1];
        for(int i=1;i<N+1;i++){
            need[i]=scn.nextInt();
            value[i]=scn.nextInt();
        }
        int[][] c = new int[N+1][M+1];
        for(int i=0;i<N+1;i++)
            c[i][0]=0;
        for(int j=0;j<M+1;j++)
            c[0][j]=0;
        for(int i=1;i<N+1;i++){
            for(int j=1;j<M+1;j++){
                if(need[i]<=j){
                    if(value[i]+c[i-1][j-need[i]]>c[i-1][j])
                        c[i][j]=value[i]+c[i-1][j-need[i]];
                    else
                        c[i][j]=c[i-1][j];
                }
                else
                    c[i][j]=c[i-1][j];
            }
        }
        scn.close();
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX