local valves = {}
local links = {}
local valveInd = {}
local working = 0
local i = 0
for line in io.lines(arg[1]) do
    local valve, flow, adj = line:match("Valve (%w+) has flow rate=(%d+); tunnels? leads? to valves? (.+)")
    if flow ~= "0" then
        working = working + 1
        valveInd[valve] = i
        i = i + 1
    end
    valves[valve] = tonumber(flow)
    links[valve] = {}
    for w in adj:gmatch("%w+") do
        table.insert(links[valve], w)
    end
end

local function getCosts(start)
    local costs, vis, Q = {}, {}, {start}
    vis[start] = true
    local steps = 0
    while #Q > 0 do
        steps = steps + 1
        local newQ = {}
        for _, p in ipairs(Q) do
            for _, cave in ipairs(links[p]) do
                if not vis[cave] then
                    vis[cave] = true
                    if valves[cave] ~= 0 then costs[cave] = steps end
                    table.insert(newQ, cave)
                end
            end
        end
        Q = newQ
    end
    return costs
end

local costs = {}
for valve, n in pairs(valves) do
    if valve == "AA" or n ~= 0 then
        costs[valve] = getCosts(valve)
    end
end

local function DFS(curr, tLeft, flow, vis, states)
    local key = string.format("%s %d %d %d", curr, tLeft, flow, vis)
    if states[key] then return states[key] end
    local max = flow
    for valve, steps in pairs(costs[curr]) do
        local rem = tLeft - steps - 1
        if rem <= 0 or bit.band(vis, bit.lshift(1, valveInd[valve])) ~= 0 then goto continue end
        max = math.max(max, DFS(valve, rem, flow + valves[valve] * rem, bit.bxor(vis, bit.lshift(1, valveInd[valve])), states))
        ::continue::
    end
    states[key] = max
    return max
end

print(DFS("AA", 30, 0, 0, {}))
local b = bit.lshift(1, working) - 1
local max = 0
for i = 1, math.floor(b/2) do
    max = math.max(max, DFS("AA", 26, 0, i, {}) + DFS("AA", 26, 0, b - i, {}))
end
print(max)