日本利用壓電磁磚將腳步轉化為電能。這些瓷磚捕捉來自你腳步的動能。當你行走時，你的重量和動作會對瓷磚產生壓力。磁磚會輕微彎曲，從而產生機械應力。磁磚內部的壓電材料將這種應力轉化為電能。每一步都會產生少量電荷，而數百萬步結合在一起就能產生足夠的電力來驅動 LED 燈、數位顯示器和感測器。在像澀谷車站這樣繁忙的地方，每天大約有 240 萬個腳步為此系統作出貢獻。這些電能可以被儲存或立即使用，從而減少對傳統電賴，並支持永續的城市基礎設施。這種方法將日常運動轉化為實用的再生能源。

唉喔唉西國引入了這種壓電磁磚來產生電力。唉喔唉西國可視為一個 $n \times m$ 的長方形，第 $i$ 行的第 $j$ 個方格有一個發電效能值 $e_{ij}$。由於設備老舊損壞，有些磁磚踩下去反而會耗電，因此 $e_{ij}$ 可能是負的。

小八覺得一格一格踩磁磚發電太慢了，因此打算騎摩托車來增加發電量。然而，由於小八還不太會騎摩托車，在騎摩托車的過程中他只能選擇加速或停下，且不能進行幅度過大的轉彎。具體而言，小八可以選擇任意格作為起點，朝任意方向開始騎車，並在第 $i$ 次衝刺中時朝某個方向 $d_i\in \{U,D,L,R\}$ 前進 $p_i(p_i \ge 1)$ 格，路徑滿足：

• $p_{i} < p_{i+1}$ : 每次前進的距離要比上一次前進的距離遠
• $d_{i}d_{i+1} \notin \{UD, DU, LR, RL\}$ : 每次前進的方向，相較於上一次不能是回頭
• 任何時刻，小八不能騎出唉喔唉西國

小八能在衝刺任意次數後選擇停下（也可以選擇 $0$ 次，此時總發電量即為起點的發電效能值）。路徑中每經過一格 $ij$，該磁磚的發電量就會增加 $e_{ij}$（包含起終點），而騎車路徑的總發電量就是所有磁磚的發電量的加總。

現在，小八好奇所有合法的路線中，最大可能的發電量是多少。不過，這個問題對他而言太困難了。你能幫他的忙嗎？