Thoát khỏi khu rừng

Khu rừng được mô tả bằng một lưới $r$ hàng và $c$ cột. Mỗi ô hoặc là một cái cây (không ai đi vào được), hoặc là ô trống. Một ô trống có thể chứa không hoặc nhiều người chơi khác. Có đúng một ô được đánh dấu là lối ra.

Bạn đang đứng ở một ô trống cho trước. Trong mỗi lượt, bạn được làm đúng một trong các việc sau:

• Đứng yên.
• Đi sang một trong bốn ô kề cạnh, với điều kiện ô đó không phải là cây.
• Nếu bạn đang đứng ở ô lối ra, bạn có thể rời khỏi khu rừng. Chỉ bạn mới được làm việc này, những người chơi khác không bao giờ rời rừng.

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

Nếu tại một thời điểm bạn và $t>0$ người chơi khác cùng đứng trên một ô thì sẽ xảy ra đúng $t$ cuộc chạm trán, sau đó cả $t$ người đó rời khỏi khu rừng. Ngay khi bạn rời khỏi khu rừng thì không còn cuộc chạm trán nào xảy ra nữa, kể cả khi ngay sau đó có người đi tới ô lối ra.

Trước khi bắt đầu, bạn phải công bố toàn bộ dãy nước đi của mình và sau đó đi đúng theo dãy đó. Vì vậy mọi người chơi khác đều biết trước lộ trình của bạn, và ai có khả năng chạm trán với bạn thì chắc chắn sẽ làm điều đó; những người không thể chạm trán sẽ đứng yên.

Hãy tìm số cuộc chạm trán nhỏ nhất mà bạn phải trải qua, nếu bạn chọn dãy nước đi tối ưu. Lưu ý bạn không cần phải đi ít bước nhất.

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 chứa $c$ ký tự mô tả một hàng của lưới:
  • T: ô có cây.
  • S: ô trống, là vị trí xuất phát của bạn.
  • E: ô trống, là lối ra.
  • Chữ số 0–9: ô trống đang có đúng số người chơi khác bằng chữ số đó.

Dữ liệu ra

Một số nguyên duy nhất là số cuộc chạm trán nhỏ nhất mà bạn phải trải qua.

Ràng buộc

• $1\le r,c\le 1000$
• Có đúng một ký tự S và đúng một ký tự E trong lưới.
• Luôn tồn tại đường đi từ ô xuất phát tới ô lối ra.

Ví dụ