Nhân dịp Olympic Miền Nam 2025 tại Tây Ninh, Ban tổ chức chuẩn bị một trò chơi trí tuệ nhằm giúp các thí sinh giao lưu với nhau. Trò chơi mang tên Gỗ trượt, lấy cảm hứng từ trò chơi quen thuộc trong giới học sinh Unblock me.

Ban tổ chức chuẩn bị một sân rộng hình chữ nhật được chia thành ~N \times M~ ô vuông đơn vị (~N,M~ là các số lẻ). Trên sân được xếp các khối gỗ hình chữ nhật kích thước ~1 \times 2~ (nằm ngang) hoặc ~2 \times 1~ (nằm dọc), được đặt sao cho:

• Không có hai khối gỗ nào chồng lên nhau.

• Chỉ có một ô trống duy nhất, tất cả các ô vuông còn lại đều được lấp kín hoàn toàn bởi các khối gỗ.

Ngoài ra, mỗi ô ~(x,y)~ trên sân được gắn với một giá trị nguyên ~A_{x,y}~ biểu thị điểm số của ô đó.

Mỗi lượt chơi, thí sinh được phép di chuyển một khối gỗ vào vị trí ô trống liền kề, theo quy tắc sau:

• Việc di chuyển phải giữ nguyên hình dạng của khối gỗ (~1 \times 2~ hoặc ~2 \times 1~), theo một trong bốn hướng lên/xuống/trái/phải.

• Các khối gỗ không được chồng lên nhau sau khi di chuyển.

• Vị trí ô trống mới sẽ nằm ở vị trí khối gỗ vừa được đẩy đi.

Thí sinh có thể thực hiện số lượng lượt di chuyển tùy ý. Gọi ~S~ là tập tất cả các ô mà ô trống từng xuất hiện tại đó trong toàn bộ quá trình chơi của thí sinh (bao gồm cả ô trống ban đầu). Tổng điểm của thí sinh đạt được là tổng các giá trị ~A_{x,y}~ với mọi ô ~(x,y)~ thuộc tập ~S~.

Yêu cầu: Hoàng là một thí sinh tham gia thi môn Tin học và muốn tận dụng lợi thế lập trình áp dụng vào trò chơi nhằm dành được nhiều điểm số nhất. Hãy giúp Hoàng viết chương trình tính tổng điểm lớn nhất có thể đạt được, bắt đầu từ vị trí ô trống ban đầu, theo các quy tắc đã nêu.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N,M~ ~(1 \le N,M \le 999)~ lần lượt là số hàng và số cột của bảng.

• Dòng thứ ~i~ trong số ~N~ dòng tiếp theo chứa ~M~ ký tự thuộc một trong ba loại 'O', 'H', 'V', '.'. Trong đó ký tự 'H' và một ký tự '.' ở phía bên phải thể hiện một thanh nằm ngang, ký tự 'V' và một ký tự '.' ở phía bên dưới thể hiện một thanh nằm dọc, và ký tự 'O' thể hiện ô trống ban đầu.

• Dòng thứ ~i~ trong số ~N~ dòng tiếp theo chứa ~M~ số nguyên, số thứ ~j~ là giá trị ~A_{i,j}~ ~(|A_{i,j}| \le 10^9)~.

Output

Một số nguyên duy nhất là số điểm cao nhất mà người chơi có thể đạt được trong màn chơi.

Scoring

Sample Input 1

3 3
H.V
H..
OH.
1 5 4
0 4 1
4 1 5

Sample Output 1

14

Notes

Tập ~S~ tối ưu là ~\{(3,1),(3,3),(1,3),(1,1)\}~.