背包问题
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("inflate.in");
ofstream out("inflate.out");
int points[10000];
int minutes[10000];
int dp[10001];
int n;
int m;
void solve()
{
int res = 0;
in>>m>>n;
for(int i=0;i<n;++i)
in>>points[i],in>>minutes[i];
memset(dp,0,sizeof(dp));
for(int i=0;i<n;++i){
for(int j=minutes[i];j<=m;++j){
dp[j] = max(dp[j-minutes[i]]+points[i],dp[j]);
}
}
out<<dp[m]<<endl;
}
int main(int argc,char *argv[])
{
solve();
return 0;
}