E=enumerate
def F(s,c,C,O,e,M,x,y,U):
 r=[]
 for X,Y in s:e[(x,y)]=e.get((x,y),[])+[((X,Y),c)];r+=(O+[(x,y)],X,Y,c-C*~-((X,Y)in U),M,U+[(X,Y)]*C),
 return r
def f(b):
 d,D={4:[]},[]
 for x,r in E(b):
  for y,v in E(r):d[K]=d.get(K:=4-(v=='$')-2*(v=='#')-3*(v=='.')-4*('@'==v),[])+[(x,y)];D+=(x,y),
 C,e=[],{};q=[([],*d[0][0],0,set(),[])]
 while q:
  O,x,y,c,M,U=q.pop(0)
  if c==len(d[3]):return c
  o={a:[(x+X,y+Y)for X in[-1,0,1]for Y in[-1,0,1]if X or Y if(P:=(x+X,y+Y))in b if[]==[1for(J,K),w in e.get((x,y),[])if(J,K)==P and w>=c]]for a,b in d.items()}
  if not M&{*o[4]}:C+=c,;q=F(o[3],c,1,*(P:=[O,e,{*o[4]},x,y,U]))+q+F(o[1],c,0,*P)+F(o[0],c,0,*P)
 return max(C+[0])
 
s1 = """
@..
.$.
...
"""
s2 = """
@....
...g$
.....
"""
s3 = """
@....
...$g
.....
"""
s4 = """
@....g..
.......$
........
.....h..
"""
s5 = """
@....z..
.......$
.....b..
"""
s6 = """
@$#.
###$
....
"""
s7 = """
@..#..
$.$g.$
...#..
"""
s8 = """
@#.d#$
$...##
e.....
..$...
##..$b
.#..g$
"""
s9 = """
..12345678
a.@....g.D
b........$
c.......#.
d......h..
"""
s10 = """
..12345678
a.@....g.D
b........$
c........#
d......h..
"""
s11 = """
..12345678
a.@....g.D
b.......#$
c........#
d......h..
"""
def to_board(D):
	return [*filter(None, D.split('\n'))]
print(f(to_board(s1)))
print(f(to_board(s2)))
print(f(to_board(s3)))
print(f(to_board(s4)))
print(f(to_board(s5)))
print(f(to_board(s6)))
print(f(to_board(s7)))
print(f(to_board(s8)))
print(f(to_board(s9)))
print(f(to_board(s10)))
print(f(to_board(s11)))

RT1lbnVtZXJhdGUKZGVmIEYocyxjLEMsTyxlLE0seCx5LFUpOgogcj1bXQogZm9yIFgsWSBpbiBzOmVbKHgseSldPWUuZ2V0KCh4LHkpLFtdKStbKChYLFkpLGMpXTtyKz0oTytbKHgseSldLFgsWSxjLUMqfi0oKFgsWSlpbiBVKSxNLFUrWyhYLFkpXSpDKSwKIHJldHVybiByCmRlZiBmKGIpOgogZCxEPXs0OltdfSxbXQogZm9yIHgsciBpbiBFKGIpOgogIGZvciB5LHYgaW4gRShyKTpkW0tdPWQuZ2V0KEs6PTQtKHY9PSckJyktMioodj09JyMnKS0zKih2PT0nLicpLTQqKCdAJz09diksW10pK1soeCx5KV07RCs9KHgseSksCiBDLGU9W10se307cT1bKFtdLCpkWzBdWzBdLDAsc2V0KCksW10pXQogd2hpbGUgcToKICBPLHgseSxjLE0sVT1xLnBvcCgwKQogIGlmIGM9PWxlbihkWzNdKTpyZXR1cm4gYwogIG89e2E6Wyh4K1gseStZKWZvciBYIGluWy0xLDAsMV1mb3IgWSBpblstMSwwLDFdaWYgWCBvciBZIGlmKFA6PSh4K1gseStZKSlpbiBiIGlmW109PVsxZm9yKEosSyksdyBpbiBlLmdldCgoeCx5KSxbXSlpZihKLEspPT1QIGFuZCB3Pj1jXV1mb3IgYSxiIGluIGQuaXRlbXMoKX0KICBpZiBub3QgTSZ7Km9bNF19OkMrPWMsO3E9RihvWzNdLGMsMSwqKFA6PVtPLGUseypvWzRdfSx4LHksVV0pKStxK0Yob1sxXSxjLDAsKlApK0Yob1swXSxjLDAsKlApCiByZXR1cm4gbWF4KEMrWzBdKQogCnMxID0gIiIiCkAuLgouJC4KLi4uCiIiIgpzMiA9ICIiIgpALi4uLgouLi5nJAouLi4uLgoiIiIKczMgPSAiIiIKQC4uLi4KLi4uJGcKLi4uLi4KIiIiCnM0ID0gIiIiCkAuLi4uZy4uCi4uLi4uLi4kCi4uLi4uLi4uCi4uLi4uaC4uCiIiIgpzNSA9ICIiIgpALi4uLnouLgouLi4uLi4uJAouLi4uLmIuLgoiIiIKczYgPSAiIiIKQCQjLgojIyMkCi4uLi4KIiIiCnM3ID0gIiIiCkAuLiMuLgokLiRnLiQKLi4uIy4uCiIiIgpzOCA9ICIiIgpAIy5kIyQKJC4uLiMjCmUuLi4uLgouLiQuLi4KIyMuLiRiCi4jLi5nJAoiIiIKczkgPSAiIiIKLi4xMjM0NTY3OAphLkAuLi4uZy5ECmIuLi4uLi4uLiQKYy4uLi4uLi4jLgpkLi4uLi4uaC4uCiIiIgpzMTAgPSAiIiIKLi4xMjM0NTY3OAphLkAuLi4uZy5ECmIuLi4uLi4uLiQKYy4uLi4uLi4uIwpkLi4uLi4uaC4uCiIiIgpzMTEgPSAiIiIKLi4xMjM0NTY3OAphLkAuLi4uZy5ECmIuLi4uLi4uIyQKYy4uLi4uLi4uIwpkLi4uLi4uaC4uCiIiIgpkZWYgdG9fYm9hcmQoRCk6CglyZXR1cm4gWypmaWx0ZXIoTm9uZSwgRC5zcGxpdCgnXG4nKSldCnByaW50KGYodG9fYm9hcmQoczEpKSkKcHJpbnQoZih0b19ib2FyZChzMikpKQpwcmludChmKHRvX2JvYXJkKHMzKSkpCnByaW50KGYodG9fYm9hcmQoczQpKSkKcHJpbnQoZih0b19ib2FyZChzNSkpKQpwcmludChmKHRvX2JvYXJkKHM2KSkpCnByaW50KGYodG9fYm9hcmQoczcpKSkKcHJpbnQoZih0b19ib2FyZChzOCkpKQpwcmludChmKHRvX2JvYXJkKHM5KSkpCnByaW50KGYodG9fYm9hcmQoczEwKSkpCnByaW50KGYodG9fYm9hcmQoczExKSkp