Đề bài

Vườn nhà Lâm được mô tả bởi một ma trận ~M \times N~, ô ở dòng ~i~, cột ~j~ gọi là ô ~(i, j)~.

Một số ô trên ma trận có trồng các cây mít, mà mít nhà Lâm thì rất lạ, nó chỉ có thể thu hoạch vào mùa đông lạnh giá.

Nhà của Lâm được đặt ở ô ~(1,1)~ và kho chứa được đặt ở ô ~(M, N)~. Lâm sẽ cưỡi một con lừa ốm yếu để đến thu hoạch các ô có mít. Vì con lừa này rất ốm yếu nên từ một ô ~(i, j)~ nào đó, nó chỉ có thể đi đến được ô ~(i+1, j)~ hoặc ô ~(i, j+1)~ mà thôi. Khi con lừa đi đến ô nào thì toàn bộ mít trên ô đó sẽ bị thu hoạch.

Một "đợt thu hoạch" là một đường đi của con lừa xuất phát từ nhà Lâm (tức ô ~(1,1)~) đến kho chứa (tức ô ~(M, N)~).

Mùa đông nên trời rất lạnh, Lâm muốn ra khỏi nhà ít lần nhất có thể, tức là Lâm muốn tối thiểu số đợt thu hoạch mà vẫn thu hoạch được hết toàn bộ số mít trong vườn.

Input

Vào từ file văn bản QQMIT.INP:

• Dòng đầu là hai số nguyên dương ~M~ và ~N~ (~M, N \leq 1000~).

• ~M~ dòng sau, mỗi dòng gồm ~N~ số ~0~ hoặc ~1~:

  • ~0~ nghĩa là ô đó không có mít.
  • ~1~ nghĩa là ô đó có mít.

Output

Ghi ra file văn bản QQMIT.OUT:

• Gồm một dòng duy nhất là số đợt thu hoạch mít tối thiểu.

Ví dụ

Sample Input

3 3
0 1 1
0 1 0
0 0 1

Sample Output

2