P1060 [NOIP2006 普及組] 開心的金明

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int v[30];
int p[30];
int dp[30010];

int main()
{
  int n,m;
  cin>>n>>m;
  for(int i = 1; i <= m; i++)
  cin>>v[i]>>p[i];
  for(int i = 1; i <= m; i++)
  {
    for(int j = n; j >= v[i]; j--)
    {
      dp[j] = max(dp[j],dp[j-v[i]] + p[i]*v[i]);
    }
  }
  cout<<dp[n]<<endl;
}