Các kỹ sư tại VRI (Viện robot Voltron) đã chế tạo thành công một đội gồm 𝑛 robot. Bất kỳ hai robot nào tương thích với nhau và đứng cùng trong một ô có thể kết hợp lại để tạo thành một robot hỗn hợp mới.

Các robot được gán nhãn theo số thứ tự từ ~1~ đến ~n (n ≤ 9)~. Hai robot được coi là tương thích nếu nhãn của chúng có số thứ tự liên tiếp nhau. Mỗi robot trong số ~𝑛~ robot ban đầu được gán ~1~ nhãn khác biệt duy nhất. Robot hỗn hợp được tạo ra bằng cách kết hợp hai robot sẽ được gán hai nhãn: là nhãn có giá trị nhỏ nhất và nhãn có giá trị lớn nhất của hai robot kết hợp tạo nên robot hỗn hợp.

Ví dụ, robot ~2~ chỉ có thể kết hợp với robot ~3~ hoặc robot ~1~. Nếu robot ~2~ kết hợp với robot ~3~, sẽ tạo ra robot hỗn hợp ~2-3~. Nếu robot ~2-3~ kết hợp với robot ~4-6~, sẽ tạo ra robot hỗn hợp ~2-6~. Robot ~1-n~ được tạo ra khi tất cả các robot kết hợp với nhau.

Các kỹ sư để ~n~ robot trong ~1~ phòng chia thành ~w × h~ ô bàn cờ, có tường vây xung quanh. Một số ô có chướng ngại vật và robot không vào được. Mỗi ô có thể chứa một hoặc nhiều robot, và một robot bao giờ cũng chỉ nằm trọn trong một ô. Ban đầu, các robot được đặt trong các ô khác nhau.

Các robot được thiết kế khá thô sơ. Chúng chỉ có thể di chuyển trên đường thẳng theo trục ~x~ hoặc trục ~y~ khi được người kỹ sư đẩy đi. Sau khi robot được đẩy theo một trong bốn hướng song song với trục ~x~ hoặc trục ~y~, robot chuyển động theo hướng được đẩy cho đến khi nó bị chặn lại bởi chướng ngại vật hoặc bởi tường. Sau khi robot dừng lại, robot tìm xem có robot nào tương thích với nó ở trong cùng ô không và kết hợp với bất kỳ robot tương thích nào mà nó tìm thấy để tạo thành robot lớn hơn. Quy trình kết hợp robot tiếp tục diễn ra cho đến khi không có thêm được sự kết hợp nào nữa.

Để giúp các robot chuyển hướng, các kỹ sư đã đặt các đĩa xoay ở một số ô. Các đĩa xoay có thể xoay theo chiều kim đồng hồ hoặc chiều ngược chiều kim đồng hồ. Một robot khi di chuyển vào ô có đĩa xoay sẽ luôn chuyển hướng ~90°~ theo hướng xoay của đĩa. Nếu robot đang dừng trên đĩa xoay được đẩy, nó sẽ xoay ~90°~ trước khi di chuyển trên đường thẳng, theo hướng vuông góc với hướng nó được đẩy đi. Tại mỗi thời điểm chỉ có một robot di chuyển.

Hãy xác định số lượng tối thiểu các lần đẩy robot sao cho tất cả n robot kết hợp với nhau (nếu có thể).

Input

• Dòng đầu tiên chứa 3 số nguyên ~n, w~ và ~h~, cách nhau với một dấu trống.
• Tiếp theo là ~h~ dòng mô tả căn phòng, mỗi dòng chứa ~w~ ký tự. Mỗi ký tự trong ~w ×h~ ký tự này biểu diễn 1 ô trong phòng. Ký tự là chữ số (~"1"~ đến ~"9"~) cho biết có 1 robot với nhãn là chữ số tương ứng nằm trong ô. Ký tự ~"x"~ cho biết có chướng ngại vật tại ô tương ứng. Ký tự ~"A"~ hoặc ~"C"~ cho biết có một đĩa xoay tại ô tương ứng. ~"a"~ cho biết đĩa xoay theo hướng ngược chiều kim đồng hồ. ~"C"~ cho biết đĩa xoay theo chiều kim đồng hồ. Tất cả các ô khác được biểu diễn bởi ký tự ~"."~.

Output

• Ghi ra một số là số lần đẩy nhỏ nhất để kết hợp cả ~n~ robot, hoặc ~-1~ nếu không kết hợp được.

Sample Input

4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...

Sample Output

5

Giới hạn

Subtask 1: ~n = 2, w ≤ 10, h ≤ 10~, và không có đĩa xoay.

Subtask 2: ~n = 2, w ≤ 10, h ≤ 10.~

Subtask 3: ~n ≤ 9, w ≤ 300, h ≤ 300. ~

Subtask 4: ~n ≤ 9, w ≤ 500, h ≤ 500.~

Nguồn: Trại đông Bảo Lộc 2021 - Thầy Đỗ Đức Đông