#include<iostream>
#include<algorithm> 
using namespace std;
int n,s,m=1,dp[1010];//s -> 背包容量 , n -> 物品个数 , m -> 命令选择
struct thing{
	int v,w,m;//p -> 物品价值 , w -> 物品重量 , m -> 物品数量 
}h[1010];
void welcome(){
	cout << "Welcome to the 'Backpack problem checker' 1.0 !" << endl;
	cout << "We can help you check if you solve the backpack problem correctly." << endl;
	cout << "Here is our command list :" << endl;
}
void print_menu(){
	cout << "#############Choose Command############" << endl;
	cout << "1 . Unlimtted backpack problem." << endl;//完全背包 
	cout << "2 . 0-1 backpack problem." << endl;//0-1背包 
	cout << "3 . Limtted backpack problem." << endl;//多重背包 
	cout << "4 . All three." << endl;//混合背包 
	cout << "5 . About." << endl;
	cout << "0 . Exit." << endl;
	cout << "#######################################" << endl;
}
void input(int type){
	if(type == 1){
		cout << "Please input each thing's value and weight." << endl;
		for(int i=1;i<=n;i++){
			cin >> h[i].v >> h[i].w;
		} 
	}else{
		cout << "Please input each thing's value , weight and how many do you have." << endl;
		for(int i=1;i<=n;i++){
			cin >> h[i].v >> h[i].w >> h[i].m;
		} 
	}
}
void UnlimttedPack(int v,int w){//完全背包（不太理解 QAQ） 
	for(int i=w;i<=s;i++){//不懂逆向枚举和顺向枚举有什么区别 
		dp[i]=max(dp[i],dp[i-w]+v);
	}
}
void LimttedPack(int v,int w,int m){//多重背包 
	for(int i=s;i>=w;i--){
		for(int j=0;j<=m;j++){
			if(i >= j*w){
				dp[i]=max(dp[i],dp[i-w*j]+v*j);
			}
		}
	}
}
int main(){
	welcome();
	while(true){
		print_menu();
		cin >> m;
		if(m == 0){
			cout << "Thanks for using !";
			return 0;
		}
		 if(m == 5){
			cout << "Backpack problem checker -- by Grace25" << endl;
			cout << "I make this because I'm studing about backpack problem." <<endl;
			cout << "I hope you like it." <<endl;
			cout << "                                 -- Grace25 , 2020.10.5" << endl;
			cout << "Something very important :" << endl;
			cout << "1 . The maxnum amount of the capacity of the bag is 1000 ." << endl;
			cout << "2 . The maxnum amount of the things you have is 1000 too ." << endl;
			continue;
		}
		cout << "Please input the capacity of the bag , how many thing do you have:" << endl;
		cin >> s >> n;
		if(m == 1){
			input(1);
			for(int i=1;i<=n;i++){
				UnlimttedPack(h[i].v,h[i].w);
			}
		}else if(m == 2){
			input(1);
			for(int i=1;i<=n;i++){
				LimttedPack(h[i].v,h[i].w,1);//0-1背包相当于只让取一个的多重背包 
			}
		}else if(m == 3){
			input(2);
			for(int i=1;i<=n;i++){
				LimttedPack(h[i].v,h[i].w,h[i].m);
			}
		}else if(m == 4){
			input(2);
			for(int i=1;i<=n;i++){
				if(h[i].m == 0)
					UnlimttedPack(h[i].v,h[i].w);
				else
					LimttedPack(h[i].v,h[i].w,h[i].m); 
			}
		}
		cout << "The maxnum amount of value in your backpack is " << dp[s] << "." <<endl;
		for(int i=1;i<=s;i++){
			dp[i]=0;
		}
	}
	return 0;
}