- 采药
- 2016-01-07 11:53:05 @
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
int dp[1005] ;
int happy[105] ;
int cost[105] ;
int main()
{
int n , time;
cin>>time ;cin>>n ;
memset(dp,0,sizeof(dp));
memset(happy,0,sizeof(happy)) ;
memset(cost,0,sizeof(cost)) ;
for(int i = 0 ; i < n ; i++)
{
cin>>cost[i]>>happy[i] ;
}
for(int i =0 ; i < n ; i++)
for(int j = time ; j >= cost[i] ; j -- ){
if( dp[j] < dp[j-cost[i]]+happy[i] )
dp[j] = dp[j-cost[i]]+happy[i] ;
// if(dp[j]<dp[j-cost[i]]+happy[i])
// dp[j] = dp[j-cost[i]]+happy[i] ;
}
cout <<dp[time]<< endl;
return 0;
}