Cho lưới n × m ô, hướng dọc tương ứng Bắc–Nam. Mỗi miền liên thông theo cạnh gồm các ô cùng chữ cái là một ngôi nhà. Các đoạn đơn vị trên biên bảng hoặc giữa hai ô thuộc hai ngôi nhà khác nhau là đường đi.

Xuất phát tại một đỉnh lưới bất kỳ trên biên Bắc, đi theo đường về phía Đông, Tây hoặc Nam; không đi lại một đoạn đường, kể cả theo chiều ngược lại. Kết thúc khi chạm biên Nam. Đường đi chia bảng thành phần phía Tây và phần phía Đông.

Tìm chênh lệch diện tích nhỏ nhất giữa hai phần. Mỗi ô có diện tích 1; một phần có thể có diện tích 0.

Đề gốc: Codeforces Gym 102552C — Прогулка по Бруклину.

Dữ liệu vào

Dòng đầu chứa n, m (1 ≤ n, m ≤ 300).

n dòng sau, mỗi dòng chứa m chữ cái Latin hoa mô tả các ô.

Kết quả

Một số nguyên là chênh lệch diện tích nhỏ nhất.

Ví dụ

Input

3 3
ABB
BAB
AAB

Output

1

Đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn. Mỗi test được chấm độc lập.