Khu rừng Biridian

Khu rừng Biridian là một lưới gồm $r$ hàng và $c$ cột. Mỗi ô hoặc là cây (không ai đi qua được), hoặc là ô trống. Trên các ô trống có thể có những người huấn luyện thú (gọi tắt là đối thủ), một ô có thể chứa từ $0$ đến $9$ đối thủ. Có đúng một ô là vị trí xuất phát của bạn và đúng một ô là cửa ra.

Mỗi lượt, bạn thực hiện một trong các hành động sau:

• Đứng yên.
• Di chuyển sang một ô kề cạnh không phải cây.
• Nếu bạn đang đứng ở cửa ra, rời khỏi khu rừng. Chỉ bạn mới được làm điều này, các đối thủ không bao giờ rời rừng.

Sau mỗi lượt đi của bạn, tất cả các đối thủ đồng thời đi một lượt (đứng yên hoặc sang ô kề cạnh không phải cây).

Nếu sau một lượt bạn đứng cùng ô với $t>0$ đối thủ thì có đúng $t$ trận đấu diễn ra, sau đó $t$ đối thủ đó rời khỏi rừng. Ngay khi bạn rời khỏi rừng thì không còn trận đấu nào nữa, kể cả khi có đối thủ vừa đi tới cửa ra. Các đối thủ không đấu với nhau.

Trước khi bắt đầu, bạn công bố công khai toàn bộ dãy nước đi của mình và sau đó đi đúng theo dãy đó. Vì vậy mọi đối thủ đều biết trước lộ trình của bạn, và mỗi đối thủ sẽ di chuyển sao cho chắc chắn có một trận đấu với bạn nếu điều đó là khả thi; đối thủ nào không thể chặn bạn thì đứng yên.

Hãy tìm số trận đấu nhỏ nhất mà bạn phải tham gia, biết rằng bạn được chọn dãy nước đi tuỳ ý (không cần ngắn nhất) và luôn tồn tại đường đi từ ô xuất phát tới cửa ra.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $r$ và $c$.
• $r$ dòng tiếp theo, mỗi dòng $c$ ký tự mô tả lưới:
  • T: ô có cây.
  • S: ô trống, vị trí xuất phát của bạn (xuất hiện đúng một lần).
  • E: ô trống, cửa ra (xuất hiện đúng một lần).
  • Chữ số 0–9: ô trống có đúng bấy nhiêu đối thủ.

Dữ liệu ra

Một số nguyên duy nhất: số trận đấu nhỏ nhất bạn phải tham gia.

Ràng buộc

• $1\le r,c\le 1000$
• Luôn tồn tại đường đi từ S tới E.

Ví dụ