include <iostream>

using namespace std;

int max(int x, int y){

return x>=y?x:y;

}

int main(){

cout<<"输入背包容量和物品数量"<<endl;

int m, //背包容量 
    n; //物品数量 

cin>>m>>n;

int table[n+1][m+1];//制表 

cout<<"输入物品的价值和重量："<<endl;

int value[n+1];
int weight[n+1];

for(int i = 1; i<=n; i++) {
    
    cin>>value[i]>>weight[i];
}

for(int k = 0; k<=n; k++)
for(int kk = 0; kk<=m; kk++){
    
    table[k][kk] = 0;
}

for(int currentSelectGood = 1; currentSelectGood <= n; currentSelectGood++)
for(int currentBableCaptable = 1; currentBableCaptable <= m; currentBableCaptable++){
    
    if(currentBableCaptable >= weight[currentSelectGood]){
        
        table[currentSelectGood][currentBableCaptable] = max(table[currentSelectGood-1][currentBableCaptable], table[currentSelectGood-1][currentBableCaptable-weight[currentSelectGood]]+value[currentSelectGood]);
    }else{
        
        table[currentSelectGood][currentBableCaptable] = table[currentSelectGood-1][currentBableCaptable];
    }
}

cout<<"最大值为："<<endl;

cout<<table[n][m];

}