package 挑战赛国赛_2022;

import java.util.Scanner;

public class test1_dfs {

    static class node{
        int x,y;
        node(int x,int y){
            this.x=x;
            this.y=y;
        }
    }

    static node[] arr;
    static boolean[] ok;//ok表示每条数据走没走过
    static int a,b,n,max=0;

    public static void dfs(int ans,int count) {//ans表示剩余可装载的重量,count表示货物数量
        max = Math.max(max,count);
        for(int i=0;i<n;i++) {
            if(ok[i]==false) {//如果这层没走过
                ok[i]=true;
                int num = arr[i].x*arr[i].y;
                if(ans>=num) {
                    dfs(ans-num,count+arr[i].y);
                }
                ok[i]=false;
            }
        }
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String str = input.nextLine();
        String name = str.split("  ")[0];
        a = Integer.parseInt(str.split("  ")[1]);
        b = Integer.parseInt(str.split("  ")[2]);
        n = input.nextInt();
        arr = new node[n];
        ok = new boolean[n];
        for(int i=0;i<n;i++) {
            int x =input.nextInt();
            int y =input.nextInt();
            arr[i] = new node(x,y);
        }
        dfs(a-b,0);
        System.out.println(name+"+"+max);
    }

}

package 挑战赛国赛_2022;

import java.util.Scanner;

public class test1_dp {

    static int a,b,n;

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String str = input.nextLine();
        String name = str.split("  ")[0];
        a = Integer.parseInt(str.split("  ")[1]);
        b = Integer.parseInt(str.split("  ")[2]);
        n = input.nextInt();
        int[] v = new int[a-b+5];//体积
        int[] w = new int[a-b+5];//价值
        for(int i=1;i<=n;i++) {
            int x = input.nextInt();
            int y = input.nextInt();
            v[i] = x*y;
            w[i] = y;
        }
        int[][] dp = new int[a-b+5][a-b+5];
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=a-b;j++) {
                if(j<v[i]) {
                    dp[i][j]=dp[i-1][j];
                }else {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
                }
            }
        }
        System.out.println(name+"+"+dp[1][2000]);
    }

}