Thành phố Byte có hệ thống giao thông gồm ~n~ đường ngang và ~m~ đường dọc chạy 2 chiều. Các đường ngang được đánh số từ 1 đến ~n~ từ trên xuống dưới và đường dọc được đánh số từ 1 đến ~m~ từ trái sang phải. Các đường ngang và đường dọc cắt nhau tạo thành ~n \times m~ giao lộ (ngã hai, ngã ba, ngã tư) như hình bên dưới. Tại các giao lộ (giao lộ ~i, j~ là giao của đường ngang thứ ~i~ với đường dọc thứ ~j~) đều có bố trí đèn giao thông gồm hai màu xanh, đỏ. Đèn màu xanh là được đi và đèn màu đỏ là đứng lại. Điểm đặc biệt của thành phố Byte là khi đèn màu đỏ thì xe ở cả bốn hướng đều phải dừng lại chờ, khi đèn màu xanh thì xe ở bốn hướng đều được đi (thẳng, rẽ trái, rẽ phải đều được). Cứ sau mỗi 1 phút thì đèn sẽ chuyển từ màu xanh sang màu đỏ và ngược lại.

Một chiếc xe khách vào thành phố ở giao lộ ~(1, 1)~ và ra khỏi thành phố ở giao lộ ~(n, m)~. Thời gian để xe khách di chuyển từ một giao lộ đến giao lộ kế cận là 1 phút. Khi xe vừa tới một giao lộ thì lúc đó đèn cũng chuyển màu, nếu là màu xanh thì xe tiếp tục đi, nếu là màu đỏ thì xe phải dừng lại chờ 1 phút để đèn chuyển màu xanh thì mới được đi tiếp.

Yêu cầu: Tìm thời gian nhanh nhất để xe khách ra khỏi thành phố.

Dữ liệu

• Dòng 1 chứa 2 số nguyên dương ~n, m~;
• ~n~ dòng tiếp theo, dòng thứ ~i~ gồm ~m~ số nguyên ~a_{ij}~ (~j = 1, 2, \dots, m~) là tình trạng đèn tại thời điểm xe bắt đầu vào thành phố: ~a_{ij} = 1~ nghĩa là tại giao lộ ~(i, j)~ có đèn màu xanh, ~a_{ij} = 0~ là tại giao lộ ~(i, j)~ có đèn màu đỏ.

Kết quả

Một số nguyên dương là số phút sớm nhất mà xe ra khỏi thành phố.

Ví dụ

Ví dụ 1

CAU3.INP

3 5
1 0 0 0 0
0 0 0 0 0
1 0 1 0 1

CAU3.OUT

6

Ví dụ 2

CAU3.INP

3 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

CAU3.OUT

13

Giới hạn

• Có 25% số test ứng với 25% số điểm của bài thỏa mãn điều kiện ~1 < n, m \le 20~;
• Có 75% số test còn lại ứng với 75% số điểm của bài thỏa mãn điều kiện ~20 < n, m \le 200~.