use strict;
use Data::Dumper;

my @x; #this holds the original values at each node
my @y; #this holds the cost
my @z; #this holds whether the item is out or not
open(FIL,"prob83data.txt");
while (<FIL>)
{
	my $l = $_;
	chomp($l);
	my @p = split(',',$l);
	push @x, \@p;
	my @v1 = split('', ('.'x80));
	push @y, \@v1;
	my @v2 = split('', ('.'x80));
	push @z, \@v2;
}
close(FIL);

$y[0][0] = $x[0][0];
my @nexts = ('1:0','0:1');
my $r = '0:0';
my $c = 80*80;

while ($c > 0)
{
	my ($i,$j) = split(':',$r);
	if ($z[$i][$j] eq '.')
	{
		$c--;
		my $v = $y[$i][$j]; #best cost up until this point
		$z[$i][$j] = '';
		$r = '';
		if ($i > 0 && $z[$i-1][$j] eq '.') #the item above isn't out
		{
			if ($y[$i-1][$j] eq '.' || ($v + $x[$i-1][$j]) < $y[$i-1][$j])
			{
				$y[$i-1][$j] = $v + $x[$i-1][$j];
			}
			push(@nexts, ($i-1). ":$j");
		}
		if ($j > 0 && $z[$i][$j-1] eq '.') #the item to the left isn't out
		{
			if ($y[$i][$j-1] eq '.' || ($v + $x[$i][$j-1]) < $y[$i][$j-1])
			{
				$y[$i][$j-1] = $v + $x[$i][$j-1];
			}
			push(@nexts, "$i:". ($j-1));
		}
		if ($i < 79 && $z[$i+1][$j] eq '.') #the item below isn't out
		{
			if ($y[$i+1][$j] eq '.' || ($v + $x[$i+1][$j]) < $y[$i+1][$j])
			{
				$y[$i+1][$j] = $v + $x[$i+1][$j];
			}
			push(@nexts, ($i+1). ":$j");
		}
		if ($j < 79 && $z[$i][$j+1] eq '.') #the item to the right isn't out
		{
			if ($y[$i][$j+1] eq '.' || ($v + $x[$i][$j+1]) < $y[$i][$j+1])
			{
				$y[$i][$j+1] = $v + $x[$i][$j+1];
			}
			push(@nexts,  "$i:". ($j+1));
		}
	}
	my $mindist = 9999999999999999;
	for (my $m = 0; $m < 80; $m++)
	{
		for (my $n = 0; $n < 80; $n++)
		{
			if ($z[$m][$n] eq '.' && $y[$m][$n] ne '.' && $y[$m][$n] < $mindist)
			{
				$mindist = $y[$m][$n];
				$r = "$m:$n";
			}
		}
	}
}

print (($y[79][79]) . "\n");