#!/usr/bin/env python

import re

RE_LINE = re.compile('^Step (.*) must be finished before step (.*) can begin.')
WORKERS=5
JOB_TIME=60
tree = dict()

def read_input():
    with open('input.txt', 'r') as f:
        for line in f:
            yield line

def add_dependency(a, b):
    if a not in tree:
        tree[a] = {
            'node': a,
            'parent': '',
            'child': '',
            'time': JOB_TIME+ord(a)-64
        } 
    if b not in tree:
        tree[b] = {
            'node': b,
            'parent': '',
            'child': '',
            'time': JOB_TIME+ord(b)-64
        } 
    tree[a]['child'] += b
    tree[b]['parent'] += a

for l in read_input():
    m = RE_LINE.match(l)
    if m is None:
        raise Exception('unpaseable line')
    add_dependency(m.group(1), m.group(2))

worker = [[0, None]] * WORKERS # time and job
total_time = 0
while len(tree):
   # finish worker job
   try:
       min_time = min([x[0] for x in worker if x[0]>0])
       total_time = min_time
   except ValueError:
       min_time = -1
   min_workers = [ k for k,v in enumerate(worker) if v[0] == min_time]
   for w in min_workers:
       job = worker[w][1]
       if job is None:
           continue
       for c in tree[job]['child']:
           tree[c]['parent'] = tree[c]['parent'].replace(job, "")
       del tree[job] 
       worker[w] = [0, None]
       print('finish job for {}({})'.format(w, job))

   # add new job
   roots = sorted([ n['node'] for n in tree.values() if len(n['parent']) == 0 and n['time']>0])
   empty_w = [ k for k,v in enumerate(worker) if v[1] is None]
   for w in empty_w:
       if len(roots) == 0:
           break
       job = roots.pop(0)
       worker[w] = (total_time+tree[job]['time'], job)
       tree[job]['time'] = 0
       print('added job for {}({})'.format(w, job))


print(total_time)