你吃過「大根蘿蔔」嗎？

據說，有一種非常大根的蘿蔔，叫作「大根蘿蔔」。由於大根蘿蔔不需特別施肥就會長得肥美，因此是許多農夫愛種的作物之一。
身為農夫的你當然也不例外，挪出了 $n$ 乘 $n$（$n\le 22$）的農田方陣種大根蘿蔔。經過了兩三個月後，每個格子都長出了一個看起來超好ㄘ的大根蘿蔔（舔）。接下來的事就只剩拔起來跟賣出去了。然而，大根蘿蔔實在太大根了！

儘管外觀沒有任何異狀，但其實大根蘿蔔們在地底下已經打成一片，造成「牽一髮而動全身」的局面了：如果拔了其中一個大根蘿蔔，那麼在他左上，上，右上，右，右下，下，左下，左的八根大根蘿蔔都會因此而受損。身為一個顧品牌的好農夫，這些受損的蘿蔔當然是不能賣出去了。

你用幾十年的種菜經驗一眼看出了每根大根蘿蔔將帶給你的利潤是多少，不過你沒辦法馬上看出到底要拔哪些大根蘿蔔才能使你的總利潤最大。請寫一個程式幫助你計算你可能獲得的最大總利潤。