#include<stdio.h> #include<string.h> #define max( a , b ) a > b ? a : b #define INF 10000000 int main () { int t , m ; int T[1050] , P[1005] ; int dp[10005] ; while( scanf("%d%d" , &t , &m )==2 ) { for( int i = 0 ; i < m ; i++ ) { scanf("%d%d" , &T[i] , &P[i] ); } memset( dp , 0 ,sizeof( dp )); for( int i = 0 ; i < m ; i++ ) for( int j = t ; j >= T[i] ; --j ) if( dp[j-T[i]]+P[i] >dp[j] ) dp[j] = dp[j-T[i]]+P[i]; printf("%d\n" , dp[t]); } return 0; }
|
请发表评论