Vào tối trước một kỳ thi tiếng Croatia rất quan trọng, phòng học đã được chuẩn bị sẵn. Ta có thể xem phòng học như một ma trận ~n \times m~, trong đó mỗi ô tương ứng với một chỗ ngồi. Mỗi ô của ma trận có thể nhận một trong ba giá trị:

• ~2~: chỗ đã có học sinh ngoan ngồi sẵn. Các bạn này có trách nhiệm nên giáo viên không lo lắng về việc quay cóp.
• ~1~: chỗ ngồi bị cấm, sẽ không có ai ngồi vào đó.
• ~0~: chỗ trống mà các học sinh nghịch ngợm có thể ngồi.

Các học sinh nghịch ngợm chưa đến lớp, nhưng sẽ đến sớm thôi. Giáo viên có thể tự quyết định các em đó sẽ ngồi vào những chỗ trống nào.

Học sinh ngoan sẽ không bao giờ quay cóp, nhưng nếu ngồi kề bên thì các em có thể khiến học sinh nghịch ngợm quay cóp. Một học sinh nghịch ngợm sẽ quay cóp nếu em ấy có ít nhất một học sinh ngồi kề ở một trong bốn hướng ~\{\text{trên}, \text{dưới}, \text{trái}, \text{phải}\}~, bất kể người kề bên đó là học sinh ngoan hay nghịch ngợm.

Hãy xác định số học sinh tối đa có thể được xếp vào phòng thi, tính cả học sinh ngoan lẫn nghịch ngợm, sao cho không xảy ra việc quay cóp nào.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~.

Mỗi trong ~n~ dòng tiếp theo chứa ~m~ ký tự, mỗi ký tự là ~0~, ~1~ hoặc ~2~, mô tả ma trận phòng học.

Output

In ra trên một dòng duy nhất tổng số học sinh lớn nhất có thể được xếp vào phòng mà không ai quay cóp.

Ràng buộc

• ~1 \le n, m \le 80~

Chấm điểm

• Subtask 1 (8 điểm): ~n, m \le 4~
• Subtask 2 (15 điểm): Mọi ô trong ma trận đều bằng ~0~
• Subtask 3 (16 điểm): ~n = 2~
• Subtask 4 (52 điểm): ~n \le 15~
• Subtask 5 (19 điểm): Không có ràng buộc bổ sung.

Sample Input 1

4 4
0100
0202
1000
2120

Sample Output 1

6

Sample Input 2

4 4
0000
0000
0000
0000

Sample Output 2

8

Giải thích

• Ví dụ 2: Giáo viên có thể xếp học sinh ở các cột lẻ của hàng ~1~ và ~3~, đồng thời ở các cột chẵn của hàng ~2~ và ~4~. Với cách này sẽ không có hai học sinh nào kề nhau theo bốn hướng, nên không ai có thể quay cóp.