index.md

為美好的地牢獻上爆擊

\begin{figure}[h] \centering \includegraphics[width=12cm]{img.jpg} \caption{和真正在向其他人炫耀自己獲得的新技能，出自動畫《為美好的世界獻上祝福！》} \end{figure}

在某次的公會任務當中，和真意外獲得了新的被動技能 : ultimate boss 3liminator - 3，簡稱 ub33。顧名思義，這是一種用來消滅魔物的強力技能，而且還不需要消耗魔力。 詳細來說，這個技能會在擁有者遇到魔物後強制進入戰鬥，在受到魔物的攻擊後，無論是否受到傷害，下一次我方攻擊時必定會消滅對手。雖然是個像是 bug 的技能，不過因為會強制加入戰鬥，還需要先吃一記傷害後才能發動，要是沒掌握好魔物出現的位置與自己的血量，那可能很快就會上西天了。

雖然聽起來很危險，不過和真已經迫不及待想要到地牢當中試試 ub33 的效果了! 地牢是一個 $n\times m$ 的地圖，左上角與右下角座標分別為 $(1,1)$ 與 $(n,m)$。有許多的魔物散布在地牢中，每個魔物的攻擊力為 $w_{ij}$，每次我們可以選擇 上/下/左/右 其中一個方向前進一格。 值得一提的是，在進到地牢的那一刻戰鬥就開始了，也就是說，如果起點就存在魔物，那就會直接進入戰鬥。

在地牢當中可能會有稀有的道具 Amazing Damage Decreaser ，簡稱 ADD ，有了 ADD ，每次遇到魔物時受到的傷害都會減少 $w_{ij}$ 點，不過最多就只是不會受到傷害，並沒有回血的功能。而因為 ADD 十分稀有，因此在地牢當中最多就只會出現一個。

和真想知道，在走到地牢出口之前他最少承受的傷害是多少，要是因為太過興奮就被幹掉，那就糟糕了。你能告訴和真承受的傷害最少是多少嗎?

\clearpage

輸入

輸入第一行包含兩個數字 $n$, $m$ 表示地圖大小。
輸入第二行包含兩個數字 $s_x$, $s_y$ 表示起點座標。
輸入第三行包含兩個數字 $e_x$, $e_y$ 表示終點座標。
接下來會有 $n$ 行輸入，每行 $m$ 個數字，表示魔物攻擊力大小 $w_{ij}$。
如果 $w_{ij}<0$ 則表示稀有道具 ADD，其數值表示 ADD 減少的傷害量。

輸出

輸出一行數字，表示和真在地牢中受到的最少傷害值。

輸入限制

• $1\le n,m\le {10}^3$
• $1\le s_x,e_x\le n$
• $1\le s_y,e_y\le m$
• $-{10}^9\le w_{ij}\le {10}^9$

子任務

\subtasks

\clearpage

範例輸入 1

3 4
1 1
3 4
6 8 3 5
5 1 6 3
9 4 1 7

範例輸出 1

24

範例說明 1

依序往下右下右右走

範例輸入 2

3 4
1 1
3 4
6 8 -3 5
5 1 6 3
9 4 1 7

範例輸出 2

19

範例說明 2

依序往右右左下下右右走