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

struct {
	int	start;
	int	end;
	int	origin;
	int 	dest;
	int	weight;
} job[1001];

struct {
	int	pos;
	int	finish;
	int 	used;
	int	carry;
} rob[21];

int i, j, simu=1, latest=-1, bestrob, num_rob, num_job, num_ports, sum;
FILE *in;

int distance( int src, int dest ) {
	return num_ports-((dest+(num_ports-src))%num_ports);
}

void assign(int j, int r ) {
	int u=0;
	u += distance( job[j].origin, rob[r].pos );
	u += (2*5) + distance(job[j].dest, job[j].origin);
	job[j].end = job[j].start + u;
	rob[r].used += u;
	rob[r].finish = job[j].end;
	rob[r].pos = job[j].dest;
	if (latest==-1 || latest<job[j].end)
		latest = job[j].end;
}	


void main() {
	in = fopen( "centauri.in", "r" );
	while (1) {
	fscanf( in, "%d %d\n", &num_ports, &num_rob );
	if ( !num_ports && !num_rob) exit(0);
	for(i=0; i<num_rob; i++) {
		fscanf( in, "%d\n", &(rob[i].carry) );
		rob[i].finish=0; rob[i].pos=1;
		rob[i].used = 0;
	}
	num_job=0;
	do {
		fscanf( in, "%d %d %d %d\n", &job[num_job].start, &job[num_job].origin,
			&job[num_job].dest, &job[num_job].weight );
	} while ( job[num_job++].weight!=-1 );	
	num_job--;
	for( i=0; i<num_job; i++ ) {
		bestrob=-1;
		for (j=0; j<num_rob; j++ ) {
			if (rob[j].carry>=job[i].weight) {
				if (rob[j].finish<=job[i].start )
					if (distance(job[i].origin,rob[j].pos)<distance(job[i].origin,rob[bestrob].pos) || bestrob==-1)
						bestrob=j;
			}
		}	
		if (bestrob==-1) {
			for (j=0; j<num_rob; j++) {
				if (rob[j].carry>=job[i].weight) {
					if (bestrob==-1
						|| rob[bestrob].finish>rob[j].finish
						|| (rob[bestrob].finish==rob[j].finish &&
						distance(job[i].origin,rob[j].pos)<distance(job[i].origin,rob[bestrob].pos)))
						bestrob=j;
				}	
			}
		}
		assign( i, bestrob );
	}
	
	printf( "Simulation %d\n", simu++ );	
	sum=0;
	for(i=0; i<num_job; i++)
		sum +=job[i].end-job[i].start;
	printf( "Average wait time   = %.3f minutes\n", ((double)sum/(double)num_job));
	sum=0;
	for(i=0; i<num_rob; i++)
		sum += rob[i].used;
	printf( "Average utilization = %.3f %%\n\n", ((double)sum*100.0/(((double)latest-1)*((double)num_rob))));
	
}
}