lanqiaoOJ 563 采药

#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std ;
typedef long long LL ;
const LL N = 1010 , M = 110 ;
LL dp[M][N] ;
int n,m ;
int t[M] , w[M] ;
int main(){
  cin >> n >> m ;
  for(int i = 1; i <= m ; i ++){
    cin >> t[i] >> w[i] ;
  }
  for(int i = 1 ; i <= m; i ++){
    for(int j = 0; j <= n ; j ++){
      dp[i][j] = dp[i-1][j] ;
      if(j >= t[i]) dp[i][j] = max(dp[i][j],dp[i-1][j-t[i]] + w[i]);
    }
  }
  cout << dp[m][n] << endl ;
  return 0 ;
}