아 맞다 우산

경재 씨는 저녁 약속에 나가기 전에 챙기지 않은 물건이 있는지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았는데, 외출했다가 돌아오는 길에 경재 씨가 외쳤다.

"아 맞다 우산!!!"

경재 씨는 외출하고 나서야 무언가를 집에 두고 왔다는 것을 떠올릴 때마다 자책감에 시달리는 게 너무 싫었다.

외출이 잦은 경재 씨는 반복되는 실수를 없애기 위해 꼭 챙겨야 할 물건을 정리해 보았다. 그런데 지갑, 스마트폰, 우산, 차 키, 이어폰, 시계, 보조 배터리 등 종류와 개수가 너무 많았다.

불필요한 움직임을 아주 싫어하는 경재 씨는 이 물건들을 최대한 빨리 챙겨서 외출하는 이동 경로를 알고 싶어 한다.

경재 씨는 한 걸음에 상하좌우로 인접한 칸으로만 움직일 수 있다.

집을 위에서 본 모습과 챙겨야 할 물건들의 위치를 알고 있을 때, 물건을 모두 챙겨서 외출하기까지 최소 몇 걸음이 필요한지 구하는 프로그램을 작성하자.

첫 번째 줄에는 집의 가로 길이 N과 세로 길이 M이 입력된다. (3 ≤ N, M ≤ 50)

두 번째 줄부터는 집의 구조가 예제 입력과 같이 주어진다.

비어 있는 곳은 '.', 벽은 '#', 경재 씨의 현재 위치는 S, 나가는 문의 위치는 E, 챙겨야 하는 물건은 종류에 상관없이 X로 입력된다.

챙겨야 하는 물건은 최대 5개까지 있을 수 있다. 집은 언제나 벽으로 둘러싸여 있고, 나가는 문은 언제나 하나이다.

S에서 출발하여 모든 물건을 챙겨서 E까지 도착할 수 있는 최소 시간을 출력한다. 모든 물건을 챙길 수 없는 경우는 주어지지 않는다.