class Graph:
    def __init__(self):
        self.graph={}
        self.rates={}
        self.nodes=set()

    def add_edge(self, a, b):
        if a not in self.nodes:
            self.nodes.add(a)
        if b not in self.nodes:
            self.nodes.add(b)
        if a not in self.graph:
            self.graph[a]=[]
        self.graph[a].append(b)

    def add_rate(self, a, rate):
        self.rates[a]=rate

    def floyd_warshall(self):
        self.distances={}
        for node1 in self.nodes:
            for node2 in self.nodes:
                self.distances[(node1, node2)]=10**5
        for node in self.nodes:
            self.distances[(node, node)]=0
            for node2 in self.graph[node]:
                self.distances[(node, node2)]=1

        for node1 in self.nodes:
            for node2 in self.nodes:
                for node3 in self.nodes:
                    self.distances[(node2, node3)]=min(self.distances[(node2, node3)], self.distances[(node2, node1)]+self.distances[(node1, node3)])


    def find_all_paths(self, maxtime):
        self.allpaths=set()
        visited=set()
        visited.add("AA")
        for node in self.nodes:
            if self.rates[node]==0:
                visited.add(node)
        def helper(path, timeleft, visited):
            visited=visited.copy()
            self.allpaths.add(" ".join(path))
            for node in self.nodes:
                if node in visited:
                    continue
                dist=self.distances[(path[-1], node)]
                if dist<timeleft:
                    visited.add(node)
                    helper(path+[node], timeleft-dist-1, visited)
                    visited.remove(node)
        helper(["AA"], maxtime, visited)
        return self.allpaths

    def released_pressure(self, path, time):
        released=0
        path=path.split()
        for i in range(1, len(path)):
            time=time-self.distances[(path[i-1], path[i])]-1
            released+=time*self.rates[path[i]]
        return released

##inputfile="test16.txt"
inputfile="input16.txt"
graph=Graph()
with open(inputfile) as myfile:
    for line in myfile:
        parts=line.strip().replace(", ",",").split()
        valve, flow, neighbs = parts[1], int(parts[4].split("=")[1][:-1]), parts[-1].split(",")
        graph.add_rate(valve, flow)
        for neighb in neighbs:
            graph.add_edge(valve, neighb)
graph.floyd_warshall()
paths1=graph.find_all_paths(30)
maxreleased=0
for path in paths1:
    maxreleased=max(maxreleased, graph.released_pressure(path, 30))

maxreleased=0
paths2=graph.find_all_paths(26)
pathpressures={}
for path in paths2:
    path_sorted=" ".join(sorted(path.split()))
    if path_sorted not in pathpressures:
        pathpressures[path_sorted]=0
    pathpressures[path_sorted]=max(pathpressures[path_sorted], graph.released_pressure(path, 26))

for path1 in pathpressures:
    nodes1=path1.split()
    for path2 in pathpressures:
        nodes2=path2.split()
        allnodes=set(nodes1+nodes2)
        if len(allnodes)+1<len(nodes1)+len(nodes2):
            continue
        maxreleased=max(maxreleased, pathpressures[path1]+pathpressures[path2])
print(maxreleased)