Một bãi cỏ hình chữ nhật trong rừng được phủ tuyết mới vào buổi sáng. Thỏ và cáo lần lượt đi qua bãi cỏ, để lại dấu chân trên tuyết. Mỗi con luôn vào ở ô góc trên bên trái và ra ở ô góc dưới bên phải. Trong lúc ở trên bãi cỏ, chúng có thể đi tới lui, chơi đùa và đi qua lại những ô đã ghé thăm.

Chia bãi cỏ thành các ô vuông. Mỗi bước di chuyển sang một ô chung cạnh, không đi chéo hay nhảy qua ô. Khi một con vật vào một ô, dấu chân của nó che phủ hoàn toàn dấu chân trước đó ở ô này. Tại mọi thời điểm có nhiều nhất một con vật trên bãi cỏ, và không con nào vào bãi cỏ nhiều hơn một lần.

Ví dụ, ba hình dưới đây lần lượt mô tả tuyết ban đầu, dấu chân sau khi một con thỏ đi qua, rồi dấu chân sau khi thêm một con cáo đi qua:

........    RRR.....    FFR.....
........    ..RRR...    .FRRR...
........    ..R.....    .FFFFF..
........    ..RRRR.R    ..RRRFFR
........    .....RRR    .....FFF

Bạn được cho bản đồ dấu chân còn nhìn thấy sau các lượt đi qua. Hãy xác định số con vật ít nhất có thể đã đi qua để tạo ra bản đồ đó.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(H,W\), là chiều cao và chiều rộng của bản đồ. Mỗi dòng trong \(H\) dòng tiếp theo chứa đúng \(W\) ký tự:

• .: tuyết chưa bị giẫm lên.
• R: dấu chân trên cùng là của thỏ.
• F: dấu chân trên cùng là của cáo.

Bản đồ mô tả dấu chân tạo ra theo các quy tắc trên và có ít nhất một ô có dấu chân.

Dữ liệu ra

Một số nguyên \(N\ge1\), là số con vật ít nhất có thể đã tạo ra bản đồ.

Ràng buộc

• \(1 \le H,W \le 4000\).

Phân nhóm

• \(30\) điểm: đáp án \(N\le200\) và \(H,W\le500\).
• \(70\) điểm còn lại: không có ràng buộc bổ sung.

Ví dụ

5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF

2