/**********************************
 **    File:       bus.c    	   **
 **    Programmer: Marc Douet    **
 **    Date:       08/08/02      **
 **********************************/

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


#define MIN_BUSES		1	/* Minimum number of buses.				*/
#define MAX_BUSES		20	/* Maximum number of buses.				*/
#define MIN_ROUTES	1	/* Minimum number of routes a bus can have.	*/
#define MAX_ROUTES	10	/* Maximum number of routes a bus can have.	*/
#define MIN_DURATION	1	/* Minimum time it takes a bus to do a route.	*/
#define MAX_DURATION	1000	/* Maximum time it takes a bus to do a route.	*/
#define TRUE		1	/* Macro for boolean true.				*/
#define FALSE		0	/* Macro for boolean false.				*/


/* Structure to hold all necessary information about each bus.			*/
typedef struct Bus {
	int	routeDurations[MAX_ROUTES];	/* Array of route durations.		*/
	int	numRoutes;				/* Number of routes this bus has.	*/
	long 	totalTravelTime;			/* Total travel time logged so far.	*/
	int 	passengerWaiting;			/* Tells if a passenger is waiting.	*/
} busInfo;


/**********************
 ** Global Variables **
 **********************/
int 		numBuses;			/* Number of buses to be read in from input.	*/
int		passengerArrivalTime;	/* Time the customer desires to ride a bus.	*/
busInfo	buses[MAX_BUSES];		/* Array of bus info objects.				*/
	


/***************************************************************************
 * Function:  gotoNextLine
 *
 * Synopsis:  void gotoNextLine(void)
 *
 * Description:  Advances the file pointer to the next line.  Needed since
 * 		     calling scanf() does not advance the file pointer to the 
 *               next line after reading the last formatted data on the line.
 *		     Note:  This should only be called after ALL data has been
 *               read from the input line of data.
 *
 * Return Value:  None.
 ***************************************************************************/  
void gotoNextLine()
{
	while(getchar() != '\n');
}


/***************************************************************************
 * Function:  clearBuffer
 *
 * Synopsis:  void clearBuffer(char *buf)
 *
 *	        buf  [IN/OUT]  The buffer to be cleared out.
 *
 * Description:  Clears out the specified buffer.
 * 		     		
 * Return Value:  None.
 ***************************************************************************/ 
void clearBuffer(char *buf)
{
	int index;

	/* Initialize the buffer to NULL.	*/
	for(index = 0; index < sizeof(buf); index++)
		buf[index] = '\0';	
}


/***************************************************************************
 * Function:  setNumRoutes
 *
 * Synopsis:  void setNumRoutes(busID)
 *
 *            busID	[IN]	The bus object to set.
 *
 * Description:  Determines how many routes a bus has by determining how
 *               many route durations are on the current line of input, and
 *		     sets the 'numRoutes' member of the bus object specified with
 *               the parameter 'busID'.  
 *               Note:  The file offset is unchanged after this call.
 * 		     		
 * Return Value:  None.
 ***************************************************************************/ 
void setNumRoutes(int busID)
{
	char	line[100];
	char	*linePtr;
	int 	routeCount = 0;
	long	filePos;

	/* Save the file offset, so we can reset it later.	*/
	filePos = ftell(stdin);

	/* Read a line from input into a character array.	*/
	gets(line);
	linePtr = line;
	
	/* Determine how many routes there are by seeing how 	*/
	/* many tokens there are in the line of input.  Note	*/
	/* that the line pointer is set to null after the 	*/
	/* first call to the tokenizer, this is because that  */
	/* after the first call, the line is stored internally*/
	/* by the tokenizer call.					*/
	while(strtok(linePtr, " ") != NULL) {
		routeCount++;
		linePtr = NULL;
	}

	/* Restore the file offset to what it was before.	*/
	fseek(stdin, filePos, SEEK_SET);

	/* Ensure that the number of routes is valid.		*/
	if(routeCount < MIN_ROUTES || routeCount > MAX_ROUTES) {
		printf("Error: %d is an invalid route count.\n", routeCount);
		exit(1);
	}

	/* Set the number of routes for this bus.			*/
	buses[busID].numRoutes = routeCount;
}

	
/***************************************************************************
 * Function:  readBusRouteDurations
 *
 * Synopsis:  void readBusRouteDurations(void)
 *
 * Description:  Reads in the list of bus route durations from input, and
 *               populates each bus info object with each bus' info.
 * 		     		
 * Return Value:  None.
 ***************************************************************************/ 
void readBusRouteDurations()
{
	int 	bus, route;
	
	/* Read in each route duration for every bus.			*/
	for(bus = 0; bus < numBuses; bus++) {
		/* Advance to the next line of input and set the 	*/
		/* number of routes for this bus.				*/
		gotoNextLine();
		setNumRoutes(bus);

		/* Initialize the remaining bus info data members.	*/
		buses[bus].totalTravelTime = 0;
		buses[bus].passengerWaiting = FALSE;

		/* Add each route duration to the bus' list.		*/
		for(route = 0; route < buses[bus].numRoutes; route++) {
			scanf("%d", &buses[bus].routeDurations[route]);
			
			/* Ensure that the route duration is valid.	*/
			if((buses[bus].routeDurations[route] < MIN_DURATION) 
				|| (buses[bus].routeDurations[route] > MAX_DURATION)) {
				printf("Error: %d is not a valid route duration.\n"
					,buses[bus].routeDurations[route]);
				exit(1);
			}
		}
	}
}


/***************************************************************************
 * Function:  getWaitTime
 *
 * Synopsis:  int getWaitTime(void)
 *
 * Description:  Determines how long a passenger has to wait for the next bus,
 *               given the desired arrival time.  This is done by adding up 
 *               route durations of each bus until a value greater or equal to 
 *               the desired arrival time is found, then the value that is the
 *               closest to the desired arrival time is subtracted from the 
 *               desired arrival time to get the actual wait time.  Note that 
 *               when a bus returns from the last route on its list, it 
 *               continues with the first route on its list, and so on, until
 *               a passenger arrives (desired arrival time is reached).
 * 		     		
 * Return Value:  The total wait time is returned.
 ***************************************************************************/ 
int getWaitTime()
{
	int	bus, route;
	long 	worstReturnTime = 50000;		/* The worst possible value of*/
								/* the return time, this is a	*/
								/* really big number.		*/
	long 	bestReturnTime = worstReturnTime;	/* The total travel time of 	*/
							 	/* bus who will be returning	*/
							 	/* first after the passenger  */
								/* arrives.  Set to the worst */
							 	/* return time initially.	*/

	/* Catch the case where the passenger arrives as all the buses are	*/
	/* leaving.  The passenger should be able to catch a bus right away in  */
	/* this case.										*/
	if(passengerArrivalTime == 0)
		return 0;

	/* For every bus, continue tallying up the total travel time until a 	*/
	/* passenger is waiting for that bus to arrive.					*/
	for(bus = 0; bus < numBuses; bus++) {
		/* While there is no passenger waiting...					*/	
		while(!buses[bus].passengerWaiting) {
			/* Tally the travel time using each duration until a 		*/
			/* passenger is waiting for this bus to return.			*/
			for(route = 0; route < buses[bus].numRoutes; route++) {
				buses[bus].totalTravelTime 
					+= buses[bus].routeDurations[route];

				/* If a passenger is waiting...				*/
				if(buses[bus].totalTravelTime >= passengerArrivalTime) {
					/* If this is the first bus to return since the */
					/* passenger began waiting, set this as the best*/
					/* return time seen so far.				*/
					if(buses[bus].totalTravelTime < bestReturnTime) 
						bestReturnTime = buses[bus].totalTravelTime;

					/* Set the flag to let this bus know it has a 	*/
					/* passenger waiting, and break from the loop.	*/
					buses[bus].passengerWaiting = TRUE;
					break;

				}
			}
		}
	}
			
	/* If no best return time was found, it means that no buses had routes,	*/
	/* so the passenger does not have to wait for a bus, so set the best 	*/
	/* return time to be the passenger arrival time.	 			*/
	if(bestReturnTime == worstReturnTime) 
		bestReturnTime = passengerArrivalTime;

	/* The wait time is the best return time subtracted from the time that	*/
	/* the passenger began waiting, return that value.				*/
	return (bestReturnTime-passengerArrivalTime);
}


/***************************************************************************
 * Function:  main
 *
 * Synopsis:  int main(void)
 *
 * Description:  Main driver of the program.  Trys to read the START tag
 *               from input.  If a START tag was found, it goes into a loop 
 *               that through each iteration:
 *                1.  Reads in the number of buses.
 *		 	2.  Reads in list of bus route durations.
 *			3.  Reads in the desired arrival time.
 *			4.  Determines and prints the wait time.
 *			5.  Reads in another START tag.
 *			 
 * Return Value:  0 if success, 1 if error was encountered.
 ***************************************************************************/ 
int main()
{
	char	tag[sizeof("START")];

	/* Initialize the tag, bus count, and desired arrival time.			*/
	clearBuffer(tag);
	numBuses = passengerArrivalTime = 0;
	
	/* Read in the START tag and bus count.						*/
	scanf("%s %d", tag, &numBuses);

	/* WHILE we have found a START tag...						*/
	while(!strcmp(tag, "START")) {
		/* Ensure that the bus count is valid.					*/
		if((numBuses < MIN_BUSES) || (numBuses > MAX_BUSES)) {
			printf("Error: %d is an invalid bus count.\n", numBuses);
			exit(1);
		}

		/* Try to read in bus route durations from input.			*/
		readBusRouteDurations();

		/* Read in the arrival time from input.					*/
		scanf("%d", &passengerArrivalTime);

		/* Ensure the arrival time is valid, must be a positive integer.	*/
		if(passengerArrivalTime < 0 || passengerArrivalTime > 32767) {
			printf("Error: The arrival time must be a positive integer.\n");
			exit(1);
		}

		/* Clear out the START/END tag to read in the END tag.		*/
        	clearBuffer(tag);
 
        	/* Read in the END tag. 							*/
        	scanf("%s", tag);  

		/* IF an END tag was not found, print an error, and exit 1. 	*/
		if(strcmp(tag, "END")) {
			printf("Error: No END tag was found after the data.\n");
			exit(1);
		}

		/* Print the duration of time the customer has to wait for a bus.	*/
		printf("%d\n", getWaitTime());

		/* Reinitialize the tag, bus count, and desired ride time.		*/
		clearBuffer(tag);
		numBuses = passengerArrivalTime = 0;

		/* Try to read in another tag and bus count.				*/
		scanf("%s %d", tag, &numBuses);
	}
	
	/* We are done with all data sets, so exit 0.					*/
	exit(0);
}