66. 旅行大閘蟹問題

在這個問題中，你是一隻因公出差的螃蟹銷售員，為了到隔壁群落推銷最新款的彈塗魚乾，你必須渡過凶險的沙河。

沙河可以視作一個$N\times M$的棋盤，棋盤中每一列由上自下編號分別為$0, 1, 2, 3, ..., N-1$，每一行由左自右編號分別為$0, 1, 2, 3, ..., M-1$，第$r$列第$c$行的座標記為$(r, c)$。
所謂渡過沙河就是從棋盤上一點$(r_s, c_s)$走到目的點$(r_t, c_t)$，中途可以選擇0個或多個地點休息。
身為一名受過良好教育的螃蟹，你深知自己應該謹守螃蟹的古老訓誡，不管身處多麼嚴酷的環境都絕對不可以直著走，因此你的旅程只能由以下三種走法組成(每一種走法都可以使用多次或不使用)：

1. 若當前座標為$(r, c)$，可以橫向走到下個休息點，停在$(r, c + t), t$可以是任意整數，但是此休息點必須在棋盤內。
2. 若當前座標為$(r, c)$，可以沿對角線方向走到下個休息點，停在$(r + t, c + t), t$可以是任意整數，但是此休息點必須在棋盤內。
3. 若當前座標為$(r, c)$，可以沿反對角線方向走到下個休息點，停在$(r + t, c - t), t$可以是任意整數，但是此休息點必須在棋盤內。

如圖所示，螃蟹當前位置在(1, 2)時，灰色 / 藍色 / 紅色格子分別代表1 / 2 / 3種走法一步可以走到的休息點。

另外，由於沙河強烈的日曬與複雜的環境，隨便亂走很可能死在半途，這也是路線規畫必須考慮的問題。
為了簡化問題，沙河上座標$(r, c)$點的環境可以由潮濕度$h(r, c)$與舒適度$p(r, c)$概述，滿足下列條件的旅程規劃可以稱為一個合法螃蟹旅程：

1. 旅程必須由$(r_s, c_s)$出發，經過數個休息點後到達$(r_t, c_t)$。其中$(r_s, c_s)$必須為第一個休息點，$(r_t, c_t)$必須為最後一個休息點，且相鄰兩個休息點必須滿足前述的走法限制。
2. 各個休息點的潮濕度，必須依經過的順序嚴格遞增，否則路途中可能會被曬成螃蟹乾。
3. 旅程的舒適度定義為路途中所有休息點的舒適度總和。

給定起點$(r_s, c_s)$、終點$(r_t, c_t)$及沙河的大小、潮濕度及舒適度資訊，請問所有合法螃蟹旅途中，舒適度最高者有多高？
若不存在任何合法螃蟹旅程，請輸出"You are fired!"。

輸入

輸入檔案中，一個檔案只會有一筆測資。
第一行有六個整數，分別為$N$、$M$、$r_s$、$c_s$、$r_t$、$c_t$。
第二行為空白行，此行除了換行符號外不會有其他字元。
接下來的$N$行每行有$M$個整數，第$r$行的第$c$個整數代表$h(r, c)$。
再來為一空白行，此行除了換行符號外不會有其他字元。
再來有$N$行每行有$M$個整數，第$r$行的第$c$個整數代表$p(r, c)$。

輸出

若存在合法螃蟹旅程，輸出最大的舒適度。
若不存在，則輸出"You are fired!" (不含括號)，請注意大小寫及標點符號必須完全一致。
輸出完後請換行。

條件限制

大測資(100%):

$2 \leq N \times M \leq 10^6$
$0 \leq h(r, c) < 10^6$
$-10 < p(r, c) < 10$
$0 \leq r_s, r_t < N$
$0 \leq c_s, c_t < M$
$(r_s, c_s) \neq (r_t, c_t)$

中測資(70%):

額外限制 $N \leq 300, M \leq 300$

小測資(30%):

額外限制 $N \leq 3, M \leq 3$

範例輸入1

2 3 0 0 1 0

0 1 2
5 3 4

1 1 1
1 1 -1

範例輸出1

5

請注意輸出最後面是有換行符號的。

範例輸入2

3 4 0 0 0 3

2 0 0 9
0 7 8 0
6 0 4 0

1 1 1 0
1 -1 5 0
1 -1 1 0

範例輸出2

7

請注意只有休息點需要滿足條件，前往休息點的路途中路過的點不需滿足潮濕度遞增，也不必算入舒適度。

範例輸入3

2 2 0 0 1 0

0 0
2 2

1 1
1 1

範例輸出3

You are fired!

請注意螃蟹不能直走，也不能走到相同潮濕度的位置休息。

小提示

彈塗魚乾事實上是一種餅乾的名稱，大閘蟹應該是不會吃彈塗魚的。

Judge Setting

run-time limit: 1500 ms
memory limit: 536870912 byte
測資數量: 9