题解 | #采药#

#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
    int T,M;
    while(cin>>T>>M){
        int Time[M];
        int Value[M];
        for(int i=0;i<M;i++){
            cin>>Time[i]>>Value[i];
        }
        int dp[T+1];
        for(int i=0;i<T+1;i++){dp[i] = 0;}
        for(int i=0;i<M;i++){
            for(int j=T;j>=Time[i];j--){
                dp[j] = max(dp[j],dp[j-Time[i]]+Value[i]);
            }
        }
        cout<<dp[T]<<"\n";
    }
}