Một kho hàng tự động được thiết kế dưới dạng lưới ô vuông kích thước ~R~ hàng và ~C~ cột. Mỗi ô trong kho có thể là:

• ~.~ : Đường đi thông thoáng.
• # : Kệ hàng cố định (không thể đi qua).
• ~D~ : Vách ngăn tự động (bình thường không đi qua được, nhưng có thể điều khiển để hạ xuống thành đường đi thông thoáng).
• ~S~ : Vị trí xuất phát của xe tự hành.
• ~E~ : Vị trí đích cần giao hàng.

Ở mỗi bước, xe tự hành có thể di chuyển sang 1 trong 4 ô kề cạnh (lên, xuống, trái, phải) với thời gian là 1 giây/bước, miễn là ô đó không phải kệ hàng #.

Hệ thống điều khiển trung tâm cho phép xe tự hành gửi lệnh hạ tối đa ~K~ vách ngăn tự động D trên hành trình để mở đường tắt (việc hạ vách ngăn diễn ra tức thời, không tốn thêm thời gian, xe đi vào ô D vẫn chỉ tốn 1 giây như ô .).

Yêu cầu: Hãy tìm thời gian ngắn nhất (tính bằng giây) để xe tự hành đi từ S đến E. Nếu không thể đến được E (dù đã dùng tối đa ~K~ lần hạ vách ngăn), hãy đưa ra -1.

Đầu vào

Dữ liệu được đọc từ tệp OLP2026_05.INP bao gồm:

• Dòng đầu tiên chứa ba số nguyên ~R,C~ và ~K~ (~2≤R,C≤500;0≤K≤10~).
• ~R~ dòng tiếp theo, mỗi dòng là một xâu độ dài ~C~ chỉ gồm các ký tự ., #, D, S, E mô tả bản đồ kho hàng (đảm bảo có đúng một chữ S và một chữ E).

Đầu ra

Kết quả được ghi vào tệp OLP2026_05.OUT gồm một số nguyên duy nhất là thời gian ngắn nhất tìm được (hoặc -1).

Ví dụ 1

Input

4 5 1
S.D.E
.###.
.#D#.
.....

Output

4

Ví dụ 2

Input

3 3 0
S#.
#D.
..E

Output

-1

Subtask

• Subtask 1 (20%): R, C ≤ 8; K ≤ 2.
• Subtask 2 (30%): R, C ≤ 50; K ≤ 5.
• Subtask 3 (50%): Theo giới hạn chung.