Nhiệm vụ của bạn là lập trình một drone trinh sát tiên tiến cho một sứ mệnh quan trọng. Drone phải điều hướng qua một địa hình phức tạp, đa dạng để đến vị trí mục tiêu. Ràng buộc chính là nguồn nhiên liệu hạn chế của drone. Các loại địa hình khác nhau tiêu thụ lượng nhiên liệu khác nhau để vượt qua.

Mục tiêu của bạn là tìm đường đi từ điểm xuất phát đến mục tiêu sao cho tiêu thụ tổng lượng nhiên liệu ít nhất.

Lưới chứa các phần tử sau:

• S: Vị trí xuất phát của máy bay.
• T: Mục tiêu của sứ mệnh.
• . (Đồng bằng): Địa hình dễ dàng, tốn 1 đơn vị nhiên liệu để tiến vào.
• ~ (Đầm lầy): Địa hình khó khăn, tốn 2 đơn vị nhiên liệu để tiến vào.
• ^ (Núi): Địa hình rất khó khăn, tốn 3 đơn vị nhiên liệu để tiến vào.
• F (Trạm nhiên liệu): Tiến vào ô này tốn 1 đơn vị nhiên liệu, nhưng khi đến nơi, nhiên liệu của drone sẽ được nạp lại ngay lập tức lên mức dung tích tối đa.
• # (Địa hình không thể vượt qua): căn cứ quân sự hoặc vùng thời tiết cực đoan

Drone bắt đầu với dung tích nhiên liệu tối đa cho trước. Nó không thể thực hiện một bước di chuyển nếu chi phí để tiến vào ô tiếp theo lớn hơn lượng nhiên liệu hiện tại của nó. Nếu nhiên liệu của máy bay giảm xuống đúng 0 khi tiến vào một ô, bước di chuyển đó vẫn được coi là hợp lệ. Nhiệm vụ của bạn là tìm chi phí nhiên liệu tối thiểu cho toàn bộ sứ mệnh.

Input

• Dòng đầu tiên chứa ba số nguyên được phân tách bằng dấu cách: \(R\) (số hàng), \(C\) (số cột), và \(F_{max}\) - dung tích nhiên liệu tối đa của máy bay
  \((1 ≤ R, C ≤ 200)\) và \((1 ≤ F_{max} ≤ 300)\).
• \(R\) dòng tiếp theo, mỗi dòng chứa một chuỗi gồm C ký tự, đại diện cho lưới sứ mệnh.

Output

• Một số nguyên duy nhất đại diện cho tổng số đơn vị nhiên liệu tối thiểu được tiêu thụ để di chuyển từ S đến T.
• Nếu không thể đến được mục tiêu do bị chặn vật lý hoặc do các hạn chế về nhiên liệu, hãy xuất ra -1.

Example

4 5 5
S~~^T
.#.##
.F...
..... 

-1