22955번 - 고양이 도도의 탈출기

고양이 도도가 강아지들을 피해 탈출구를 찾아 방을 탈출하려 하고 있다. 

고양이 도도는 현재 위치한 공간의 상태에 따라 다음과 같이 움직일 수 있다.

• 고양이가 위치한 곳에 사다리가 존재하거나 고양이가 위치한 곳이 아래가 뚫려있는 공간이 아닌 상태에서 고양이가 위치한 곳의 아래 칸에 사다리가 존재한다면 각각 위 칸과 아래 칸으로 이동할 수 있고 사다리를 이용하여 한 칸 이동할 시 5만큼의 체력이 소모된다.
• 고양이가 위치한 곳이 아래가 뚫려 있는 공간이라면 고양이는 아래에 있는 바닥 중 가장 처음 마주한 바닥에 착지하게 되며 이때 10만큼의 체력이 소비된다.
• 고양이가 아래가 뚫려 있는 공간에 위치해 있지 않을 경우, 좌우로 1칸씩 이동할 수 있으며 1칸 이동할 시 1만큼의 체력이 소비된다.

이때, 평평한 바닥 위에서의 이동과 사다리 타기, 바닥으로 착지하는 행동은 별개의 행동으로 본다. 예시로 고양이 도도가 사다리가 있는 위치로 1칸 이동한 후 사다리를 타고 1칸을 올라간다면 총 6만큼의 체력이 소비된다. 고양이 도도가 체력을 가장 적게 소비하며 탈출하고자 할 때 고양이 도도는 얼마의 체력으로 탈출할 수 있을까?

첫째 줄에 방의 높이 $N$ ($ 2 \leq N \leq 1\,000$)과 방의 너비 $M$ ($ 2 \leq M \leq 1\,000$)이 주어진다. 

둘째 줄부터 $N$개의 줄에 공간의 상태가 주어진다. 공간의 상태는 $C$, $D$, $E$, $F$, $L$, $X$로 이루어져 있고, 아래와 같은 의미를 가진다.

• $C$: 고양이 도도
• $D$: 강아지
• $E$: 탈출구
• $F$: 일반 바닥
• $L$: 사다리
• $X$: 아래가 뚫려있는 공간

고양이와 탈출구는 방안에 각각 하나씩 있으며 아래가 뚫려있는 공간을 제외하고는 모든 위치에 평평한 바닥이 존재한다. 가장 아래 바닥의 경우에는 아래가 뚫려 있는 공간이 올 수 없다.

고양이 도도가 체력을 가능한 적게 소비하며 방을 탈출하려 할 때, 총 얼마의 체력으로 방을 탈출할 수 있을지 소비된 체력을 출력한다.

방을 탈출하지 못할 경우에는 dodo sad를 출력한다.