#include <stdio.h>
#include <stdlib.h>

int i,j, M, V, max, indeks;
int *fi, *pi, *ci,cst;
int *final;

int *protoci, *dobit, *opt, *ind;

int main(int argc, char *argv[])
{
	scanf("%d", &V);
	scanf("%d", &M);
	
	protoci = (int *)malloc(sizeof(int)*M);
	dobit = (int *)malloc(sizeof(int)*M);
	
	fi = (int *)malloc(sizeof(int)*M);
	pi = (int *)malloc(sizeof(int)*M);
	ci = (int *)malloc(sizeof(int)*M);
	final = (int *)malloc(sizeof(int)*M);
	
	opt = (int *)malloc(sizeof(int)*(V + 1));
	ind = (int *)malloc(sizeof(int)*(V + 1));
	
	for (i = 0; i <= V; i++)
	{
		opt[i]=-1;
		ind[i]=-1;
	}
	
	opt[0]=0;
	
	for (i=0; i < M; i++)
	{
		scanf("%d%d%d",&fi[i], &pi[i], &ci[i]);				
	}
	
	scanf("%d",&cst);
	
	for (i=0; i < M; i++)
	{
		protoci[i] = fi[i];
		dobit[i] = pi[i] * cst - fi[i] * ci[i];
		final[i] = 0;
	}	
	
	max=0;
	
	for (i=1; i <= V; i++)
	{
		for (j=0; j < M; j++)
		{
			if (i>=protoci[j] && opt[i-protoci[j]] != -1 && opt[i] < opt[i-protoci[j]] + dobit[j])
			{
				opt[i]=opt[i-protoci[j]] + dobit[j];
				ind[i]=j;
			}
		}
		if (opt[i] > opt[max]) max=i;
	}
	
	//printf("Dobit je: %d \n", opt[max]);
	//printf("Agregati: \n");

	indeks = max;

	while(ind[indeks] > -1)
	{
		//printf(" %d ", protoci[ind[indeks]]);
		final[ind[indeks]] += 1;
		indeks= indeks - protoci[ind[indeks]];
	}

	//printf("\n------\n");
	
	for (j=0; j < M; j++)
		if(final[j] != 0)
		printf("%-6d%-6d\n",j+1,final[j]*protoci[j]);
	
	return(0);
}
