【模板】01背包

import java.util.*;
public class  Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int bag = sc.nextInt();
        int[][] gift = new int[num][2];
        for (int i = 0; i < num; i++) {
            gift[i][0] = sc.nextInt();
            gift[i][1] = sc.nextInt();
        }
        System.out.println(getMaxValue(gift, bag));
        System.out.println(getfullbag(gift,bag));
    }
    private static int getMaxValue(int[][] gift, int bag ) {
        int[][] dp = new int[gift.length + 1][bag + 1];
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1 ; j < dp[0].length; j++) {
                if (j - gift[i - 1][0] >= 0 ) {
                    dp[i][j] = Math.max(dp[i - 1][j - gift[i - 1][0]] + gift[i - 1][1],
                                        dp[i - 1][j]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[gift.length][bag];
    }
    private static int getfullbag(int[][] gift, int bag) {
        int[][] dp = new int[gift.length + 1][bag + 1];
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1 ; j < dp[0].length; j++) {
                int left = j - gift[i - 1][0] ;
                if (left >= 0 ) {
                    if(left > 0){
                        if(dp[i-1][left] == 0){
                            dp[i][j] = dp[i-1][j];
                        }else{
                            dp[i][j] = Math.max(dp[i - 1][j - gift[i - 1][0]] + gift[i - 1][1],dp[i - 1][j]);
                        }
                    }else{
                        dp[i][j] = Math.max(gift[i - 1][1],dp[i - 1][j]);
                    }
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[gift.length][bag];
    }
}