#include <iostream>
#include <vector>
#include<string.h>
using namespace std;

int main() {
	// your code goes here
	const int MAX_MONEY=10001;
	vector<int> calories;
	vector<int> moneys;
	vector<int> nos;
	vector<int> types;
	int n,d,no,d2,d3;
	int dp[MAX_MONEY],dp2[MAX_MONEY],dp3[MAX_MONEY];
	int up;
	memset(dp,-1,sizeof(dp));
	memset(dp2,-1,sizeof(dp2));
	memset(dp3,-1,sizeof(dp3));
	cin>>up;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>d>>no>>d2>>d3;
		types.push_back(d);
		nos.push_back(no);
		moneys.push_back(d2);
		calories.push_back(d3);
	}
	dp2[0]=0;
	for(int k=0;k<2;k++){
		for(int i=(k==0?0:300);i<up;i++){
			if(dp2[i]==-1)continue;
			for(int j=0;j<moneys.size();j++){
				if(types[j]!=k)continue;
				if(i+moneys[j]>up)continue;
				d2=i+moneys[j];
				d3=dp2[i]+calories[j];
				if(dp2[d2]<d3){
					dp2[d2]=d3;
					dp[d2]=nos[j];
				}
			}
		}
	}
	memset(dp2,-1,sizeof(dp2));
	memset(dp3,-1,sizeof(dp3));
	for(int i=up;i>0;i--){
		if(dp[i]==-1){
			continue;
		}
		d=(dp2[i]==-1?0:dp2[i])+calories[dp[i]];
		d2=i-moneys[dp[i]];
		if(dp2[d2]<d){
			dp2[d2]=d;
			dp3[d2]=nos[dp[i]];
		}
	}
	int p=0,c=0;
	cout<<"最高カロリーになるメニューは\n";
	while(dp3[p]!=-1){
		cout<<dp3[p]<<"番のメニュー ";
		p=p+moneys[dp3[p]];
	}
	
	return 0;
}