import java.util.*;
import java.util.Scanner;

/*
*动态规划思想解决0/1背包问题
*/
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        System.out.println("输入背包的容量");
        int bagCap=in.nextInt();  //背包的容量
        System.out.println("总共有多少个物品");
        int n=in.nextInt();  //总共有多少个物品
        int[][] mono=new int[2][n];  // 2行n列，第一行表示物品的重量，第二行表示物品的价值
        int[][] dp=new int[n][bagCap+1]; //表，数组下标从0开始，加1防止数组溢出
        System.out.println("依次输入物品的重量和价值");
        for(int i= 0;i<n;i++){
            mono[0][i]=in.nextInt();
            mono[1][i]=in.nextInt();
        }
        //自低向上打表，先初始化最低层,最低层应该是数组中的倒数第一行，对应的数组下标就是n-1
        for(int j=0;j<=Math.min(mono[0][n-1]-1,bagCap);j++){
            dp[n-1][j]=0;
        }
        for(int j=mono[0][n-1];j<=bagCap;j++){
            dp[n-1][j]=mono[1][n-1];
        }
        //开始自低向上打表,要始终记住数学符号的含义：dp[i][j] 表示可选物品是i,i+1,.......,n，背包容量是j时问题的最优解
        for(int i=n-2;i>=1;i--){
            for(int j=0;j<Math.min(mono[0][i]-1,bagCap);j++){
                dp[i][j]=dp[i+1][j];
            }
            for(int j=mono[0][i];j<=bagCap;j++){
                dp[i][j]=Math.max(dp[i+1][j],dp[i+1][j-mono[0][i]]+mono[1][i]);
            }
        }
        //打表到最顶层时的处理
        if(bagCap<mono[0][0]){
            dp[0][bagCap]=dp[1][bagCap];
        }else{
            dp[0][bagCap]=Math.max(dp[1][bagCap],dp[1][bagCap-mono[0][0]]+mono[1][0]);
        }
        System.out.println("最优解是："+dp[0][bagCap]);
    }
}