동적 계획 질문 - "게임 왕"은 각 게임에 하나의 성취치를 표시하는 동시에 모든 게임에 대해 통관에 필요한 일수를 추산한다. 그는 앞으로 X일 내에 자신이 게임을 할 수 있는 성취를 최대로 달성할 계획이다.

import java.util.Scanner;

/*
    ：
            ，  J      ，        ，                。
       ，               ！             ，      “   ”。
                         ，        ，        。         
，              ，                    ，      X               
，           ？（              ，                   ，              1 ）

    
         N X，       ，  N       N(1<=N<=10)，X              (1<=X<=1000)。

      1       A1(0<=A1<=10000)            B1  (1<=Bi<=500)        。

 N+1    N      An(0<=An<=10000)            Bn (1<=Bn<=500)        

    
            。


    
2 2
10 1
20 2
    
20

  
     :
3 4
10 2
18 3
10 2
     :
20
 */
public class Q2 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //         N X，       ，  N       N(1<=N<=10)，X              (1<=X<=1000)。
        int n = in.nextInt();
        int x = in.nextInt();
        //      1       A1(0<=A1<=10000)            B1  (1<=Bi<=500)        。
        // N+1    N      An(0<=An<=10000)            Bn (1<=Bn<=500)        
        int [] val = new int[n];
        int [] days = new int[n];

        for (int i = 0; i < n; i ++) {
            val[i] = in.nextInt();
            days[i] = in.nextInt();
        }
        in.close();

        //    
        //dp[i][j],       j,  i         

        //      
        //dp[i][j] = max (dp[i - 1][j], dp[i - 1][ j - days[i - 1] ] + val[i - 1])

        int [][] dp = new int[n + 1][x + 1];

        //    0             0
        for (int i = 1; i <= n; i++) {
            dp[i][0] = 0;
        }
        //   0                 0
        for (int j = 0; j <= x; j++) {
            dp[0][j] = 0;
        }
        //   java      0，   

        for (int i = 1; i <= n; i ++) {
            for (int j = x; j >= 0; j --) {
                if (j < days[i - 1]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - days[i - 1]] + val[i - 1]);
                }

            }
        }

        System.out.println(dp[n][x]);
    }
}