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

#define BUFFER_SIZE 128
#define MAX_TUNNELS 16
#define MAX_VALVES 128
#define MAX_TIME 26

typedef struct valve {
    char name[2];
    int ppm;
    char nextValveNames[16][2];
    struct valve **nextValves;
    int valve_count;
} VALVE;

unsigned findBestPPM(VALVE, VALVE, int, unsigned, VALVE*, int, VALVE*, int, VALVE*, int, int, int);
unsigned bestMax = 0;
int bestPpm = 0;

int main() {
    char buf[BUFFER_SIZE], *p, c;
    memset(buf, 0, BUFFER_SIZE);
    p = buf;
    VALVE valves[MAX_VALVES], curr;
    int valve_count = 0;

    while ((c = getchar()) != EOF) {
        *p++ = c;
        if (c == '\n') {
            p = buf;
            memset(&curr, 0, sizeof(VALVE));
            sscanf(p, "Valve %c%c has flow rate=%i; tunnels lead to valve", &curr.name[0], &curr.name[1], &curr.ppm);
            if (curr.ppm > bestPpm) {
                bestPpm = curr.ppm;
            }
            while(*p++ != 'v') {}
            while(*p++ != 'v') {}
            while(*p++ != ' ') {}
            while(*p != 0) {
                sscanf(p, "%c%c", &curr.nextValveNames[curr.valve_count][0], &curr.nextValveNames[curr.valve_count][1]);
                curr.valve_count++;
                while(*p != ',' && *p != 0) p++;
                if (*p == ',') p+=2;
            }
            curr.nextValves = (VALVE**)malloc(curr.valve_count * sizeof(VALVE*));
            memset(curr.nextValves, 0, curr.valve_count * sizeof(VALVE*));
            valves[valve_count] = curr;
            valve_count++;
            memset(buf, 0, BUFFER_SIZE);
            p = buf;
        }
    }

    // Create pointers instead of names
    for (int i = 0; i < valve_count; i++) {
        for (int j = 0; j < valves[i].valve_count; j++) {
            for (int k = 0; k < valve_count; k++) {
                if (valves[k].name[0] == valves[i].nextValveNames[j][0] && valves[k].name[1] == valves[i].nextValveNames[j][1]) {
                    valves[i].nextValves[j] = &valves[k];
                    break;
                }
            }
        }
    }

    // Find the starting point 'AA'
    for (int i = 0; i < valve_count; i++) {
        if (valves[i].name[0] == 'A' && valves[i].name[1] == 'A') {
            curr = valves[i];
            break;
        }
    }

    VALVE *opened = (VALVE*)malloc(2 * MAX_TIME * sizeof(VALVE));
    memset(opened, 0, 2 * MAX_TIME * sizeof(VALVE));
    VALVE *walked = (VALVE*)malloc(MAX_TIME * sizeof(VALVE));
    memset(walked, 0, MAX_TIME * sizeof(VALVE));
    VALVE *elephantWalked = (VALVE*)malloc(MAX_TIME * sizeof(VALVE));
    memset(elephantWalked, 0, MAX_TIME * sizeof(VALVE));
    printf("%u\n", findBestPPM(curr, curr, MAX_TIME, 0, opened, 0, walked, 0, elephantWalked, 0, 0, 0));
    free(opened);
    free(walked);
    free(elephantWalked);
    for (int i = 0; i < valve_count; i++) {
        free(valves[i].nextValves);
    }
}

unsigned findBestPPM(VALVE valve, VALVE elephantValve, int time, unsigned sum, VALVE* opened, int opened_count, VALVE* walked, int walk_length, VALVE* elephantWalked, int elephantWalk_length, int skipNext, int elephantSkipNext) {
    unsigned max = 0, tmp = 0;
    if (time <= 0) {
        return sum;
    }

    for (int i = 1; i < time; i++) {
        tmp += bestPpm * (time - i);
    }
    // If we have no chance of beating the highScore, just skip
    if (bestMax > sum + tmp) {
        return sum;
    }
    tmp = 0;

    VALVE walked_copy[MAX_TIME];
    for (int i = 0; i < MAX_TIME; i++) {
        walked_copy[i] = walked[i];
    }
    VALVE elephantWalked_copy[MAX_TIME];
    for (int i = 0; i < MAX_TIME; i++) {
        elephantWalked_copy[i] = elephantWalked[i];
    }
 
    // Shouldn't run in circles
    // Magyarorszag elore megy nem hatra
    for (int i = 0; i < walk_length; i++) {
        if (walked[i].name[0] == valve.name[0] && walked[i].name[1] == valve.name[1]) {
            return sum;
        }
    }
    for (int i = 0; i < elephantWalk_length; i++) {
        if (elephantWalked[i].name[0] == elephantValve.name[0] && elephantWalked[i].name[1] == elephantValve.name[1]) {
            return sum;
        }
    }


    // Both can move
    if (!skipNext && !elephantSkipNext) {
        // Not opening, just running on both
        for (int i = 0; i < valve.valve_count; i++) {
            for (int j = 0; j < elephantValve.valve_count; j++) {
                walked[walk_length] = valve;
                elephantWalked[elephantWalk_length] = elephantValve;
                tmp = findBestPPM(*valve.nextValves[i], *elephantValve.nextValves[j], time - 1, sum, opened, opened_count, walked, walk_length + 1, elephantWalked, elephantWalk_length + 1, 0, 0);
                for (int k = 0; k < MAX_TIME; k++) {
                    walked[k] = walked_copy[k];
                }
                for (int k = 0; k < MAX_TIME; k++) {
                    elephantWalked[k] = elephantWalked_copy[k];
                }
                if (max < tmp) {
                    max = tmp;
                }
            }
        }

        // Opening human valve only
        if (valve.ppm > 0) {
            tmp = 0;
            for (int i = 0; i < opened_count; i++) {
                if (opened[i].name[0] == valve.name[0] && opened[i].name[1] == valve.name[1]) {
                    tmp = 1;
                    break;
                }
            }
            if (!tmp) {
                unsigned openedPressure = valve.ppm * (time-1);
                for (int i = 0; i < valve.valve_count; i++) {
                    opened[opened_count] = valve;
                    walked[0] = valve;
                    for (int j = 0; j < elephantValve.valve_count; j++) {
                        elephantWalked[elephantWalk_length] = elephantValve;
                        tmp = findBestPPM(*valve.nextValves[i], *elephantValve.nextValves[j], time - 1, sum + openedPressure, opened, opened_count+1, walked, 1, elephantWalked, elephantWalk_length + 1, 1, 0);
                        for (int k = 0; k < MAX_TIME; k++) {
                            elephantWalked[k] = elephantWalked_copy[k];
                        }
                        if (max < tmp) {
                            max = tmp;
                        }
                    }
                }
            }
        }

        // Opening elephantValve only
        if (elephantValve.ppm > 0) {
            tmp = 0;
            for (int i = 0; i < opened_count; i++) {
                if (opened[i].name[0] == elephantValve.name[0] && opened[i].name[1] == elephantValve.name[1]) {
                    tmp = 1;
                    break;
                }
            }
            if (!tmp) {
                unsigned openedPressure = elephantValve.ppm * (time-1);
                for (int i = 0; i < elephantValve.valve_count; i++) {
                    opened[opened_count] = elephantValve;
                    elephantWalked[0] = elephantValve;
                    for (int j = 0; j < valve.valve_count; j++) {
                        walked[walk_length] = valve;
                        tmp = findBestPPM(*valve.nextValves[j], *elephantValve.nextValves[i], time - 1, sum + openedPressure, opened, opened_count+1, walked, walk_length + 1, elephantWalked, 1, 0, 1);
                        for (int k = 0; k < MAX_TIME; k++) {
                            walked[k] = walked_copy[k];
                        }
                        if (max < tmp) {
                            max = tmp;
                        }
                    }
                }
            }
        }

        // Both opening
        if (elephantValve.ppm > 0 && valve.ppm > 0 && !(elephantValve.name[0] == valve.name[0] && elephantValve.name[1] == valve.name[1])) {
            tmp = 0;
            for (int i = 0; i < opened_count; i++) {
                if (opened[i].name[0] == elephantValve.name[0] && opened[i].name[1] == elephantValve.name[1]) {
                    tmp = 1;
                    break;
                }
            }
            for (int i = 0; i < opened_count; i++) {
                if (opened[i].name[0] == valve.name[0] && opened[i].name[1] == valve.name[1]) {
                    tmp = 1;
                    break;
                }
            }
            if (!tmp) {
                unsigned openedPressure = elephantValve.ppm * (time-1) + valve.ppm * (time-1);
                opened[opened_count] = elephantValve;
                opened[opened_count+1] = valve;
                elephantWalked[0] = elephantValve;
                walked[0] = valve;
                for (int i = 0; i < elephantValve.valve_count; i++) {
                    for (int j = 0; j < valve.valve_count; j++) {
                        tmp = findBestPPM(*valve.nextValves[j], *elephantValve.nextValves[i], time - 2, sum + openedPressure, opened, opened_count+2, walked, 1, elephantWalked, 1, 0, 0);
                        if (max < tmp) {
                            max = tmp;
                        }
                    }
                }
            }
        }
    } else if (skipNext && !elephantSkipNext) {
        // Human is opening valve, only elephant has a choice
        for (int i = 0; i < elephantValve.valve_count; i++) {
            elephantWalked[elephantWalk_length] = elephantValve;
            tmp = findBestPPM(valve, *elephantValve.nextValves[i], time - 1, sum, opened, opened_count, walked, walk_length, elephantWalked, elephantWalk_length + 1, 0, 0);
            for (int k = 0; k < MAX_TIME; k++) {
                elephantWalked[k] = elephantWalked_copy[k];
            }
            if (max < tmp) {
                max = tmp;
            }
        }

        // Opening this valve if it was not opened before
        //
        // Only consider this if the flow rate here is > 0
        if (elephantValve.ppm > 0) {
            tmp = 0;
            for (int i = 0; i < opened_count; i++) {
                if (opened[i].name[0] == elephantValve.name[0] && opened[i].name[1] == elephantValve.name[1]) {
                    tmp = 1;
                    break;
                }
            }
            if (!tmp) {
                unsigned openedPressure = elephantValve.ppm * (time-1);
                for (int i = 0; i < elephantValve.valve_count; i++) {
                    opened[opened_count] = elephantValve;
                    elephantWalked[0] = elephantValve;
                    tmp = findBestPPM(valve, *elephantValve.nextValves[i], time - 1, sum + openedPressure, opened, opened_count+1, walked, walk_length, elephantWalked, 1, 0, 1);
                    if (max < tmp) {
                        max = tmp;
                    }
                }
            }
        }
    } else if (!skipNext && elephantSkipNext) {
        // Elephant is opening valve???, only human has a choice
        for (int i = 0; i < valve.valve_count; i++) {
            walked[walk_length] = valve;
            tmp = findBestPPM(*valve.nextValves[i], elephantValve, time - 1, sum, opened, opened_count, walked, walk_length + 1, elephantWalked, elephantWalk_length, 0, 0);
            for (int k = 0; k < MAX_TIME; k++) {
                walked[k] = walked_copy[k];
            }
            if (max < tmp) {
                max = tmp;
            }
        }

        // Opening this valve if it was not opened before
        //
        // Only consider this if the flow rate here is > 0
        if (valve.ppm > 0) {
            tmp = 0;
            for (int i = 0; i < opened_count; i++) {
                if (opened[i].name[0] == valve.name[0] && opened[i].name[1] == valve.name[1]) {
                    tmp = 1;
                    break;
                }
            }
            if (!tmp) {
                unsigned openedPressure = valve.ppm * (time-1);
                for (int i = 0; i < valve.valve_count; i++) {
                    opened[opened_count] = valve;
                    walked[0] = valve;
                    tmp = findBestPPM(*valve.nextValves[i], elephantValve, time - 1, sum + openedPressure, opened, opened_count+1, walked, 1, elephantWalked, elephantWalk_length, 1, 0);
                    if (max < tmp) {
                        max = tmp;
                    }
                }
            }
        }
    }

    if (max > bestMax) {
        bestMax = max;
    }
    return max;
}