lanqiaoOJ 554 开心的金明

#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std ;
typedef long long LL ;
const LL N = 30010 , M = 30 ;
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] ;
    w[i] = w[i] * t[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 ;
}