采药 (Java代码）

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		 Scanner sc = new Scanner(System.in);
	     int T=sc.nextInt(); 
	     int n=sc.nextInt();
	    
	     int[]dp=new int[T+1];
	     for (int i = 1; i<=n; i++) {
		    
	    	 int t=sc.nextInt();//时间
	    	 int v=sc.nextInt();//价值
	    	 int s=1;
	    	 for (int j = 1;  j <=s;  s-=j,j*=2) {
				for (int k =T; k>=j*t; k--) {
					dp[k]=Math.max(dp[k], dp[k-j*t]+j*v);
				}
			}
		}
	     System.out.println(dp[T]);
	}
}