#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
typedef struct {
	bool* elem;//Says if borrel i is part of the subset
	int size;//Amount of borrels that are part of the subset
	int n;
}Subset;

typedef struct Obligations{
	int r;//Start of interval
	int d;//End of interval
	int p;//Time slots required by the obligation
}Obligation;

void parser(int* t, int* m, int** b, int* n, Obligation*** I, int** nI);

void stringify(int att,int m, int*s, int n, Subset** whenObligation, Obligation** I, int* nI){
	for(int h=0;h<m-1;h++){
		printf("%d,", s[h]+1);
	}
	printf("%d\n",s[m-1]+1);
	for(int i=0;i<n;i++){
		for(int j=0;j<nI[i];j++){
			bool first = true;
			for(int k=0;k<whenObligation[i][j].n;k++){
				if(whenObligation[i][j].elem[k]){
					if(!first)printf(",");
					first = false;
					printf("%d",k+I[i][j].r+1);
				}
			}
			printf("\n");
		}
	//	bool borrelAtTime[t];
	//	for(int j=0;j<t;j++)borrelAtTime[j]=false;
	//	for(int h=0;h<att[i]->n;h++)
	//		if(borrelSubset->elem[h])
	//			for(int j=s[h];j<b[h]+s[h];j++)
	//				borrelAtTime[j] = true;
	//	for(int j=0;j<nI[i];j++){
	//		
	//		for(int k=I[i][j].r;k<=I[i][j].d;
	//	}
	}
	printf("%d\n",att);

	
}

int borrel(int t, int m, int* b, int n, int* s,Subset** whenObligation, Obligation** I, int* nI);

bool borrelSubsetCanAttend(int t,Subset* borrelSubset,int* b,int* s,Obligation *obligations,int n,Subset* whenObligation);

bool borrelIterate(int t,int m,int* b,int* s);

void subsetInitSize(Subset* subset, int size, int n){
	subset->size = size;
	subset->n = n;
	int i=0;
	for(i=0;i<n-size;i++){
		subset->elem[i]=false;
	}
	for(;i<n;i++){
		subset->elem[i]=true;
	}
}
bool subsetIterate(Subset* subset);

void subsetInit(Subset* subset,int n);


void main(){
	int t,m,n; int* b; int* nI; Obligation** I;
	parser(&t,&m,&b,&n,&I,&nI);
	//Subset set;
	//bool elems[] = {true,true,true,true};
	//set.elem = elems;
	//set.size=4;
	//set.n=4;

	//printf("{%d,%d,%d,%d}\n",set.elem[0],set.elem[1],set.elem[2],set.elem[3]);
	//while(subsetIterate(&set)){
	//	printf("{%d,%d,%d,%d}\n",set.elem[0],set.elem[1],set.elem[2],set.elem[3]);
	//}
	////set.n=2;
	////printf("%d\n",borrelSubsetCanAttend(t,&set,b,s,I[0],nI[0]));
	//Subset att[n];
	int s[m];
	Subset** whenObligation;
	whenObligation = malloc(sizeof(Subset*)*n);
	for(int i=0;i<n;i++){
		whenObligation[i] = malloc(sizeof(Subset)*nI[i]);
		for(int j=0;j<nI[i];j++){
			subsetInit(whenObligation[i]+j, I[i][j].d-I[i][j].r+1);
		}
	}
	int att = borrel(t,m,b,n,s,whenObligation,I,nI);
	stringify(att,m,s,n,whenObligation,I,nI);

}

void parseIntegers(int n, int* a){
	char str[n*10];
	scanf("%s",str);
	for(int i=0;i<n;i++){
		char* num;
		if(i==0)
			num = strtok(str,",");
		else
			num = strtok(NULL,",");
		a[i] = atoi(num);
	}
	
}

void parser(int* t, int* m, int** b, int* n, Obligation*** I, int** nI){
	scanf("%d",t);
	scanf("%d",m);

	*b = malloc(sizeof(int)**m);
	parseIntegers(*m, *b);
	//char borrelLengths[200];
	//scanf("%s",borrelLengths);
	//for(int h=0;h<*m;h++){
	//	char* borrelLength;
	//	if(h==0)
	//		borrelLength = strtok(borrelLengths,",");
	//	else
	//		borrelLength = strtok(NULL,",");
	//	(*b)[h] = atoi(borrelLengths);
	//}

	scanf("%d",n);
	*nI = malloc(sizeof(int)**n);
	*I = malloc(sizeof(Obligation*)**n);
	for(int i=0;i<*n;i++){
		char str[300];
		scanf("%s",str);
		char* num = strtok(str,",");
		(*nI)[i] = atoi(num);
		(*I)[i] = malloc(sizeof(Obligation)*(*nI)[i]);

		for(int j=0;j<(*nI)[i];j++){
			char* num;
			num = strtok(NULL,",");
			(*I)[i][j].r = atoi(num)-1;
			num = strtok(NULL,",");
			(*I)[i][j].d = atoi(num)-1;
			num = strtok(NULL,",");
			(*I)[i][j].p = atoi(num);
		}

	}

	return;
}

void subsetInit(Subset* subset,int n){
	subset->size = n;
	subset->n = n;
	subset->elem = malloc(sizeof(bool)*n);
	for(int i=0;i<n;i++)subset->elem[i]=true;
}

bool fixedSizeSubsetIterate(Subset* subset){
	int i=subset->n-1;
	for(int j=0; j<subset->n-subset->size; j++){
		for(;subset->elem[i];i--);
		if(j<subset->n-i-1){
			int k;
			subset->elem[i]=true;
			for(k=i+1;k<=i+1+j;k++)
				subset->elem[k] = false;
			for(;k<subset->n;k++)
				subset->elem[k] = true;
			return true;
		}
		i--;
	}
	return false;
}

bool subsetIterate(Subset* subset){
	if(subset->size==0)return false;
	if(!fixedSizeSubsetIterate(subset)){
		subsetInitSize(subset,subset->size-1,subset->n);
		//subset->size--;
		//int i;
		//for(i=0;i<subset->n-subset->size;i++){
		//	subset->elem[i]=false;
		//}
		//for(;i<subset->n;i++){
		//	subset->elem[i]=true;
		//}
	}
	return true;
}

//bool iterationCombinator(/*list of functions*/iterators,int n ,/*datatype*/x){
//	for(int i=0;i<n;i++)
//		if(!iterators[i](x))break;
//}
//}
bool obligationoverlap(int t, Subset* whenObligation,int n,Obligation* obligations,bool* borrelAtTime){
	bool obligationAtTime[t];
	for(int i=0;i<t;i++)obligationAtTime[i]=false;
	for(int i=0;i<n;i++){
		for(int j=obligations[i].r;j<=obligations[i].d;j++){
			if(whenObligation[i].elem[j-obligations[i].r]){
				if(obligationAtTime[j]||borrelAtTime[j])return true;
				obligationAtTime[j]=true;
			}
		}
	}
	return false;
}
bool borrelSubsetCanAttend(int t,Subset* borrelSubset,int* b,int* s,Obligation *obligations,int n,Subset* whenObligation){
	//TODO: Put this in a seperate function
	bool borrelAtTime[t];
	for(int i=0;i<t;i++)borrelAtTime[i]=false;
	for(int h=0;h<borrelSubset->n;h++)
		if(borrelSubset->elem[h])
			for(int i=s[h];i<b[h]+s[h];i++)
				if(borrelAtTime[i])return false;
				else borrelAtTime[i] = true;

	for(int i=0;i<n;i++){
		int leftover=0;
		for(int j=obligations[i].r;j<=obligations[i].d;j++){
			leftover+=!borrelAtTime[j];
		}
		if(leftover<obligations[i].p)return false;
	}

	for(int i=0;i<n;i++){
		whenObligation[i].n = obligations[i].d-obligations[i].r+1;
		whenObligation[i].size = obligations[i].p;
		subsetInitSize(whenObligation+i,obligations[i].p,obligations[i].d-obligations[i].r+1);
	}
	//printf("start\n");
	while(obligationoverlap(t,whenObligation,n,obligations,borrelAtTime)){
		//print when obligation
		//for(int i=0;i<n;i++){
		//	printf("Obligation %d:",i+1);
		//	for(int j=0;j<whenObligation[i].n;j++){
		//		printf(" %d", whenObligation[i].elem[j]);
		//	}
		//	printf("\n");
		//}
		
		bool endOfIteration = true;
		for(int i=0;i<n;i++){
			if(fixedSizeSubsetIterate(whenObligation+i)){
				endOfIteration=false;
				break;
			}else{
				subsetInitSize(whenObligation+i,whenObligation[i].size,whenObligation[i].n);
			}
		}
		if(endOfIteration)return false;
	}
	//printf("end\n");
	return true;
}

bool borrelIterate(int t,int m,int* b,int* s){
	for(int h=0;h<m;h++){
		s[h]++;
		if(s[h]+b[h]<=t)
			return true;
		else
			s[h]=0;
	}
	return false;
}

// Input:
// t:	Amount of time slots
// m:	Amount of borrels
// b:	Amount of time slots per borrel
// n:	Amount of students
// I:	List of obligations per student
// nI:	Amount of obligations per student

// Output:
// s:	Time slot that a borrel starts
// att: The set of of borrels that a student can attend
// return==-1: There is no feasible solution
// return>=0: Amount of students that can attend the borrels in the optimum solution
int borrel(int t, int m, int* b, int n, int* s_opt,Subset** whenObligation, Obligation** I, int* nI){
	//Checks if the borrel lengths are smaller than
	//the amount of time slots
	
	int*s=malloc(sizeof(int)*m);
	for(int h=0;h<m;h++){
		s_opt[h] = 0;
		s[h] = 0;
	}

	for(int h=0;h<m;h++){
		if(b[h]>t)return(-1);
	}
	int maxAttendance = -1;

	//Initially makes all borrels start at zero
	memset(s,0,sizeof(int)*m);
	do{
		int attendance = 0;
		for(int i=0;i<n;i++){
			Subset borrelSubs;
			subsetInit(&borrelSubs,m);
			int maxAttendanceForStudent = 0;
			do{
				Subset whenObligationTmp[nI[i]];
				for(int j=0;j<nI[i];j++){
					subsetInit(whenObligationTmp+j, I[i][j].d-I[i][j].r+1);
				}
				
				if(!borrelSubsetCanAttend(t,&(borrelSubs),b,s,I[i],nI[i],whenObligationTmp))
					continue;
				if(borrelSubs.size>maxAttendanceForStudent){
					maxAttendanceForStudent = borrelSubs.size;
					for(int j=0;j<nI[i];j++){
						whenObligation[i][j] = whenObligationTmp[j];
					}
					
				}
			}while(subsetIterate(&(borrelSubs)));
			attendance+=maxAttendanceForStudent;
		}
		if(maxAttendance<attendance){
			maxAttendance=attendance;
			for(int h=0;h<m;h++)s_opt[h]=s[h];
		}
		//printf("{%d,%d} %d\n", s[0],s[1],attendance);
	}while(borrelIterate(t,m,b,s));
	return(maxAttendance);
}