Thành phố Y 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ộ. Tại các giao lộ đều có bố trí đèn giao thông gồm hai màu xanh đỏ. Đèn xanh là được đi và đèn đỏ là đứng lại. Điểm đặc biệt của đèn ở đây là khi đèn đỏ thì xe ở cả bốn hướng đều phải dừng lại chờ, khi đèn xanh thì xe ở bốn hướng đều được đi. Cứ sau mỗi 1 phút thì đèn sẽ chuyển từ xanh sang đỏ và ngược lại.

Một chiếc xe khách muốn 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 trờ 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 để chuyển xanh thì mới được đi tiếp.

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

Input

• Dòng đầu tiên là hai số nguyên ~n~ và ~m~ (~2 \le n, m \le 1000~);
• ~n~ dòng tiếp theo, dòng thứ ~i~ gồm ~m~ số nguyên ~a_{ij}~ 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à có đèn màu đỏ.

Output

• Gồm một số nguyên dương là số phút thời gian nhanh nhất để xe đi ra khỏi thành phố.

Sample Input 1

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

Sample Output 1

6