在某個國家，為了讓所有城市排列整齊，政府將所有城市以$m$行$n$列的矩陣方式排列，且為了省錢只建造了左-右、上-下、左上-右下，三種方向的道路。
現在有一個商人從第$0$行第$0$列的城市出發，在不同城市及道路上進行交易，且每次皆只會走向右、下、右下三個方向的道路。
已知：
在第$i$行$j$列的城市可以賺取$p_{i,j}$的錢
在第$i$行$j$列城市通往右方城市的道路上可以賺取$a_{i,j}$的錢
在第$i$行$j$列城市通往下方城市的道路上可以賺取$b_{i,j}$的錢
在第$i$行$j$列城市通往右下方城市的道路上可以賺取$c_{i,j}$的錢
且某些道路因為法令關係而無法通過，請問此商人在抵達第$m$行$n$列的城市前最多可以賺取多少錢

輸入格式

第一行有兩個正整數，分別代表$m$, $n$ 接下來有$m\ast n$行，每行有四個正整數，分別代表第$i$行第$j$列的$p_{i,j}$、$a_{i,j}$、$b_{i,j}$、$c_{i,j}$（$0<=i<m$，$0<=j<n$，以$(0,0),(0,1),(0,2),...,(m-1.n-1)$的順序排列），若該道路無法通過則輸入-1。

輸出格式

輸出商人最多可以賺取多少錢

範例輸入

2 3
1 7 3 -1
5 10 8 2
4 -1 -1 -1
4 5 -1 -1
3 4 -1 -1
2 -1 -1 -1

範例輸出

30

提示

BFS？還是其實有其他方法