#!/usr/bin/perl -w

use v5.36;
use strict;

my %flow;
my %tun;

while (<>) {
	chomp;
	my ($v, $f, $n) = /Valve (..) has flow rate=(\d+);.* to valves? (.*)/;
	$flow{$v} = $f if $f;
	$tun{$v} = [ split /, /, $n ];
	say $n;
}

sub bfs($start) {
	my %seen;
	my @q = [ $start, 0 ];
	while (@q) {
		my $st = shift @q;
		my ($node, $len, @path) = @$st;
		next if $seen{$node};
		$seen{$node} = [ $len, @path ];

		for my $neigh (@{ $tun{$node} }) {
			push @q, [ $neigh, $len+1, @path, $node ];
		}
	}
	return \%seen;
}

my %paths;
for my $node ('AA', keys %flow) {
	$paths{$node} = bfs($node);
}

my @q = [ 'AA', 30, 0, { }, [ ] ];

my $max = 0;
while (@q) {
	my $st = shift @q;
	my ($node, $mins, $total, $opened, $path) = @$st;
	say "At $node $total $mins ", join(',', @$path);
	if ($total > $max) {
		$max = $total;
	}
	for my $n1 (keys %{ $paths{$node} }) {
		next if !$flow{$n1};
		my $dist = $paths{$node}{$n1}[0];
		next if $opened->{$n1};

		my $m1 = $mins - $dist - 1;
		next if $m1 < 0;
		my %o1 = (%$opened, $n1 => 1);
		say " opening $n1 at $m1 ", $flow{$n1}*($m1);
		push @q, [ $n1, $m1, $total + $flow{$n1}*($m1),
			\%o1, [ @$path, $n1 ] ];
	}
}

say $max;
