帶著殖民擴張的野心，Pear和他的星際艦隊登上X星球的某平原。為了評估這塊土地的潛在價值，Pear把它劃分成了M*N格，每個格子上用一個整數(shù)（可正可負）表示它的價值。

    Pear要做的事很簡單——選擇一些格子，占領這些土地，通過建立圍欄把它們和其它土地隔開。對于M*N的格子，一共有(M+1)*N+M*(N+1)條圍欄，即每個格子都有上下左右四個圍欄；不在邊界上的圍欄被相鄰的兩個格子公用。大概如下圖【p1.png】所示。

    圖中，藍色的一段是圍欄，屬于格子1和2；紅色的一段是圍欄，屬于格子3和4。
    
    每個格子有一個可正可負的收益，而建圍欄的代價則一定是正的。

    你需要選擇一些格子，然后選擇一些圍欄把它們圍起來，使得所有選擇的格子和所有沒被選的格子嚴格的被隔開。選擇的格子可以不連通，也可以有“洞”，即一個連通塊中間有一些格子沒選。注意，若中間有“洞”，那么根據(jù)定義，“洞”和連通塊也必須被隔開。

    Pear的目標很明確，花最小的代價，獲得最大的收益。

輸入第一行兩個正整數(shù)M N，表示行數(shù)和列數(shù)。
接下來M行，每行N個整數(shù)，構成矩陣A，A[i,j]表示第i行第j列格子的價值。
接下來M+1行，每行N個整數(shù)，構成矩陣B，B[i,j]表示第i行第j列上方的圍欄建立代價。
特別的，B[M+1,j]表示第M行第j列下方的圍欄建立代價。
接下來M行，每行N+1個整數(shù)，構成矩陣C，C[i,j]表示第i行第j列左方的圍欄建立代價。
特別的，C[i,N+1]表示第i行第N列右方的圍欄建立代價。

一行。只有一個正整數(shù)，表示最大收益。

零基礎同學可以先學習視頻課程，包含C/C++、Python、百練、藍橋杯輔導、算法數(shù)據(jù)結構等課程，提供視頻講解以及配套習題，還有老師答疑，點擊這里了解課程詳情

藍橋杯