Giải bài trực tuyến

         Aladdin rất thích đi khám phá vùng hoang mạc quanh thành Baghdad. Vào một đêm sáng trăng trời quang mây tạnh, Aladdin tình cờ phát hiện ra một cửa hang bí mật. Trong hang là một mê cung cực kì phức tạp. Sợ rằng nếu đâm đầu vào thì không tìm được đường ra, Aladdin không vội vào ngay mà về nhà tìm hiểu kĩ càng.

         Sau nhiều ngày mài mông ở kho sách tìm đọc các tư liệu cổ, Aladdin phát hiện ra rằng mê cung này được vua Midas năm xưa xây lên để giấu kho báu. Mê cung có thể xem là một hình chữ nhật kích thước NxM, được tạo thành từ các phòng hình vuông. Mỗi phòng có nhiều nhất 4 phòng kề cạnh theo 4 hướng Đông, Tây, Nam, Bắc. Trong mỗi phòng có thể có cửa thông đến 2 phòng kề cạnh về phía Đông và Tây, hoặc 2 phòng kề cạnh theo hướng Bắc và Nam, hoặc cả bốn phòng kề cạnh. Có một số phòng không có cửa thông sang bất kì phòng nào. Một điều đặc biệt ở mê cung này (do bùa phép của vua Midas) : giả sử A và B là 2 phòng kề cạnh. Từ A chỉ có thể trực tiếp đi đến B (hoặc ngược lại) nếu phòng A có cửa thông đến B và B cũng có cửa thông qua A (1).

         Aladdin nhận thấy mê cung nếu để nguyên thì không thể tìm được đường đến kho báu. Vậy là phải nhờ đến thần đèn : mỗi phép của thần đèn sẽ thêm các cánh cửa ma thuật vào một phòng nào đó, làm cho phòng này có đủ cả 4 cửa thông sang các phòng bên cạnh. Dĩ nhiên thần đèn không giúp đỡ không công : số phép sử dụng càng nhiều thì phần kho báu mà Aladdin phải chia cho thần đèn càng lớn. Vậy nên Aladdin sẽ cố tìm một đường đi đến kho báu mà cần phải thay đổi ít phòng nhất.

         Biết rằng cửa hang dẫn trực tiếp đến phòng ở góc Tây Nam (dưới trái), còn kho báu nằm trong phòng ở góc Đông Bắc (phải trên).

Yêu cầu

         Cho biết kích thước và miêu tả của mê cung. Hãy tính xem cần phải thay đổi ít nhất bao nhiêu phòng để tìm được đường đi từ cửa hang đến phòng chứa kho báu.

Input

         Dòng thứ nhất gồm 2 số nguyên dương M và N (kích thước mê cung)

         M dòng sau là bảng S kích thước MxN mô tả mê cung.

                 S[i,j] = ‘+’ : có đường đến 4 phòng kề cạnh

                 S[i,j] = ‘-’  : có đường đến 2 phòng kề phía Đông và Tây

                 S[i,j] = ‘|’  : có đường đến 2 phòng kề phía Bắc và Nam

                 S[i,j] = ‘.’  : không thông sang phòng nào bên cạnh

         Giải thích câu (1) : giả sử A, B, C là 3 phòng liền kề theo thứ tự từ Đông sang Tây và được miêu tả bằng dãy "|+-" thì chỉ có thể di chuyển giữa 2 phòng B và C (thứ 2 và thứ 3). Do từ A không có đường qua B nên từ B cũng không thể qua A.

Giới hạn

         Trong tất cả các test M, N <= 2000;  

         Subtask 1 (33%) : M,  N <= 50

         Subtask 2 (67%) : Không có giới hạn của M, N

Output

         Một số nguyên dương duy nhất là số phòng ít nhất cần được thay đổi.

Example

Input 1:

3 2
|--|+.
2 3

|--
|+.

Output 1:

1

Input 2:

3 3

|||
|||
|||

Output 2:

3