在某一個遙遠的角落，有一個叫做感恩國的繁榮國家，此國人民人人都懷抱著感恩的心過著快樂的生活。但因為人口增加的太快了，因此大家決定挖一個跟地面上一樣大的城市。從此整個國家分為上、下兩個城市，因為這個特色，國家也改名為上下國。過了幾百年後，上下國的國王發現兩個城市的居民互動非常的少，跟歷史上記載以前感恩國的溫馨情景完全不一樣，國王為了讓上下兩城市的居民交流，也要讓冷漠的上下國恢復成以前的感恩國，因此融合上下國和感恩國這兩個名稱，成為了「卡恩國」，並舉辦了「跑跑卡恩車」這個比賽。

雖然這個比賽是上下城的感情交流賽，但你只是一個普通的程式設計員，單純肖想著比賽的獎金，你也知道一定有很多人也跟自己一樣，因此絕對需要事先準備好獲勝的方法。現在國王已經公佈了比賽的規則和場地，也公佈了競賽用的車種，請你照著這些條件用你的專長寫一個程式找一條能夠最快到達終點的路。

比賽規則︰

• 路上的卡比獸都已經被驅離了，不用怕會被擋住。
• 比賽期間若要上廁所請到場地的四個角落，各有一個高級的廁所供大家使用。
• 最重要的!!! 請懷著感恩的心參加這個比賽。

比賽用的車種︰

• 因為設計的關係，只能往前後左右四個方向走。
• 這是老舊的車種，兩格之間的高度差只能小於等於5，否則會翻車。
• 有龐大的油箱，不用擔心中途還需要加油。
• 車子越輕跑越快。
• 有獨特的設計，爬坡和下坡耗的油量相等，每走一格皆需消耗一公升的汽油。

比賽場地︰

• 場地是一個大小為M*N格的矩形丘陵地（0 < M、N < 100）。
• 每一格皆有一個高度值（0 <= 高度值 <= 100 ）。
• 格子的座標為(1,1)~(m,n)。
• 起點在 (1,1) 終點在 (m,n)。
• 每個場地一定能夠到達終點。

現在你要寫一個程式輸出從起點到終點最短所需要走的格數，方便你帶剛好的油量讓車子能用最快的速度跑到終點。