#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>



#define IO_ERROR 3
#define DEPENDENCY_LOOP 2
#define BAD_INPUT_FORMAT 1
int main(int argc, char *argv[]) {

	static uint32_t prereq[26] = {0};
	uint32_t incomplete = 0;
	int error;
	int now;

	/* Grab all the input rules. */

	{
		FILE *input;
		error = IO_ERROR;
		if (input = fopen(argc > 1? argv[1]: "input.txt", "r")) {
			#define MAX_INPUT_WIDTH 50
			static char buf[MAX_INPUT_WIDTH];
			error = 0;
			while (fgets(buf, MAX_INPUT_WIDTH, input)) {
				char pre, step;
				static char format[] =
					"Step %c must be finished before step %c can begin.";
				error = BAD_INPUT_FORMAT;
				if (
					buf[strlen(buf) - 1] == '\n' &&
					sscanf(buf, format, &pre, &step) == 2 &&
					'A' <= pre && pre <= 'Z' &&
					'A' <= step && step <= 'Z'
				) {
					error = 0;
					prereq[step - 'A'] |= 1 << pre - 'A';
					incomplete |= 1 << pre - 'A' | 1 << step - 'A';
				}
				if (error) break;
			}
			fclose(input);
		}
		if (error) return error;
	}

	/* Schedule ready tasks to available workers until all are
	 * complete or progress is blocked by a dependency loop. */

	{
		struct worker {
			uint32_t taskbit;
			int ready_at;
		};

		#define NUM_WORKERS 5
		#define MIN_DELAY 61
		static struct worker workers[NUM_WORKERS] = {0};
		uint32_t in_progress = 0;
		int soonest = 0;

		while (incomplete) {
			struct worker *w;
			int task;
			uint32_t taskbit;

			/* Leap into the bright future */
			now = soonest;
//			printf("now: %d\n", now);

			/* Sunday too far away */
			soonest = INT_MAX;

			/* Find workers with completed tasks */
			for (w = workers; w < workers + NUM_WORKERS; ++w) {
//				printf("Worker %d: ready at %d\n", w-workers, w->ready_at);
				if (w->taskbit && w->ready_at <= now) {
//					printf("Worker %d completed task\n", w-workers);
					in_progress &= ~w->taskbit;
					incomplete &= ~w->taskbit;
					w->taskbit = 0;
				}
			}

			/* Find a free worker */
			for (w = workers; w < workers + NUM_WORKERS; ++w) {
				if (!w->taskbit) {

					/* Find a ready task */
					for (task = 0, taskbit = 1; task < 26; ++task, taskbit <<= 1) {
						if ((taskbit & incomplete & ~in_progress) && !(prereq[task] & incomplete)) {

							/* Assign that task to the worker */
//							printf("Worker %d assigned task %c\n", w-workers, task+'A');
							w->taskbit = taskbit;
							in_progress |= taskbit;
							w->ready_at = now + MIN_DELAY + task;
							break;
						}
					}
				}

				/* Find the earliest a worker will become ready */
				if (w->taskbit && w->ready_at < soonest) soonest = w->ready_at;
			}

			/* Make sure something is still happening */
			if (incomplete && !in_progress) {
				error = DEPENDENCY_LOOP;
				break;
			}
		}
	}

	printf("%d\n", now);
	return error;
}