//,map$w[$'][$_]=$\=1e9,@@for@@=0..map$S[$_]=<>,0..<>;
$w[$`][$&]=$w[$&][$`]=$'*/ .* /for<>;
for$m(@@){//,map$w[$'][$_]-=$-=$w[$'][$_]-$w[$'][$m]-$w[$m][$_],@@for@@}
//,map$'-$_&&($\-=$-=$\-$S[$']-$S[$_]-$w[0][$']-$w[$'][$_]-$w[$_][@S-2]),@@for@@=1..@S-3;
print