在某個國家，為了讓所有城市排列整齊，政府將所有城市以\(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*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？還是其實有其他方法