前情提要：

出題者和最愛瑞希教主沒有任何關係，高雄中學程式設計社也和Maimai玩家專業模仿中心沒有任何關係。本題只是為了讓題目敘述增加趣味而使用了最愛瑞希教主的名字及其相關設定。本場比賽和出題者本人都沒有任何營利目的，一旦有侵權行為我們也會立即做出更正。特此聲明。

「唉......」

最愛瑞希教主甦醒了，醒來後發現自己正躺在一張陌生的床上，旁邊躺著一位褐毛美人------日向千夏。

「來，小最，抱一個！」

日向千夏開心得向最愛瑞希教主衝過來，和他緊緊相擁著

...

... 等等，好像哪裡怪怪的？

觸感和以前不太一樣，而且千夏那嬌小的身形也沒能被我完全抱住。

身高... 比以前高？？

「妳... 不是日向千夏。」最愛瑞希教主緩緩說道。

「小最，你在說什麼？」

「為什麼要偽裝成我老婆？妳是誰... 等等，我好像看得出來。」

仔細端詳了這個充滿違和感的千夏之後，我繼續回答：

「妳是星空凜，對吧？」

站在我對面的「假」千夏只是微微地笑了一下。

「呀咧呀咧」

說完，她把手伸向了頭上，就像開蓋子一樣，把自己的頭殼打開了...

...頭殼下的另一顆頭，是一個長著橘色頭髮的頭。

「雖然很接近，但還是答錯了呢，是我北澤育美噠！！！」

「啊啊啊啊啊啊啊啊啊！！！」最愛瑞希教主瞬間驚醒。

「原來是夢喔...？」

這他□的到底什麼怪夢？

他深吸了一口氣。

「這裡是...」

他充滿警戒心地望向四周，但除了髒兮兮的地板、有些破舊的牆壁和長滿蜘蛛網的天花板外，唯一可疑的地方，就是他身旁的粉毛美人------曉山瑞希。

「你醒了啊。」

曉山瑞希蹲在最愛瑞希教主的身旁，眼神中充滿了關切。

「我和奏他們來過，這裡...似乎是不捉□就出不去的房間呢！」

「等等等等等... 蛤？」最愛瑞希教主整個人愣住了。

「開玩笑的。這裡是...哇好巧哦K怎麼又見到妳了，妳也被困在這裡了嗎?」

最愛瑞希教主也看見了...

...宵崎奏的臉P在皇城セツナ的身體上。

「等一下！瑞希！你忘記之前的教訓了嗎？」

瑞希興奮地要往奏的方向跑去，最愛瑞希教主只能趕緊拉住瑞希的手，不讓他做出危險的行為。

還好皇城セツナ沒有多管他們，自顧自的進入其中一間房間...

...

然後最愛瑞希教主和曉山瑞希突然聽到登登登登登的聲音，下一秒皇城セツナ就被從房間裡射出的芒果汁擊倒在地。

「臥槽！這裡到底是什麼破地方？」

「我們被困在一個有\(n\times m\)個房間的古屋中。」瑞希開始解釋起來。

「嗯。」

「每個房間都可以用座標\((i,j)\)表示，其\(x\)座標為\(i(1\leq i\leq n)\)，表示從左往右數第\(i\)個房間；其\(y\)座標為\(j(1\leq j\leq m)\)，表示從上往下數第\(j\)個房間。」

「嗯。」

「每個房間都只能走到其上下左右的房間。」

「如果下面沒有房間呢？」

「當然就沒辦法往下走了。同理類推。」

「所以我們到底要怎麼離開這裡？」

「我們現在在\(x\)座標\(=1\)的某個房間中。我們只需要從這裡想辦法走到\(x\)座標\(=n\)的房間就可以出去了。」

「那還不簡單。我們就一直往右走就行了啊！」最愛瑞希教主興奮道。

「問題是除了\(x\)座標\(=1\)和\(x\)座標\(=n\)的房間以外，每個房間內都有一個正整數\(a_{(i,j)}\)。」

「那有什麼了不起。」

「問題是我們走過的房間內的數字總和X，代表離開這裡後你需要在CiRCLE聽互刪相乘唱小星星的次數。」

「那如果我不聽呢？」

「那你要陪我打真人版音擊。」瑞希興奮地說。

「你□□的。」

「那麼，芒果汁又是怎麼回事？」最愛瑞希教主又問。

「有\(k\)個房間有登登登登登，這些房間的座標分別為\((x_i,y_i)\)，\(1\leq i\leq k\)。登登登登登會發出登登登登登的聲音並且對曼哈頓距離小於等於\(r_i\)的房間射出芒果汁。」

「曼哈頓距離是什麼呢？」

「座標為\((x_1,y_1)\)的房間和座標為\((x_2,y_2)\)的房間的曼哈頓距離為\(\vert (x_1-x_2)\vert +\vert (y_1-y_2)\vert\)。」

「那被芒果汁噴到就會像皇城セツナ一樣被擊倒在地上嗎？」

「對。不過，保證\(x\)座標\(=1\)和\(x\)座標\(=n\)的房間都不會被芒果汁噴到。」

「那我們不就只能隨機盲走然後祈禱不被芒果汁噴到嗎？」

「放心，我這裡有地圖，紀錄了每個房間的數字\(a_{(i,j)}\)以及所有登登登登登的資訊。」

「好，那我們走吧！」

為了保護最愛瑞希教主的耳朵，請你用程式算出從\(x\)座標\(=1\)的某個房間走到\(x\)座標\(=n\)的某個房間的過程中，房間的數字和X的最小值。

Input

第 \(1\) 列有 \(3\) 個正整數，分別為 \(n(3\leq n\leq 1002), m(1\leq m\leq 1000), k(0\leq k\leq 16068)\) 。

接下來有 \(m\) 列，每列有 \((n-2)\) 個正整數，第 \(j\) 列的第 \(i\) 個正整數是座標為 \((i+1,j)\) 的房間的的數字 \(a_{(i+1,j)}(1\leq a_{(i+1,j)}\leq 2\times 10^5, \forall 2\leq i+1\leq (n-1), 1\leq j\leq m)\)。

再接下來有 \(k\) 列，其中第 \(i\) 列有 \(3\) 個整數 \(x_i(1\leq x_i \leq n),y_i(1\leq y_i \leq m),r_i(0\leq r_i \leq 499)\) ，分別代表有登登登登登的房間的 \(x\) 座標、 \(y\) 座標和題敘中的 \(r_i\) 。

Output

輸出一個整數，代表房間的數字和X的最小值。如果根本走不到 \(x\) 座標 \(=n\) 的房間，請輸出 \(-1\) 。

Constraints

第 \(1\) 組測資， \(1 \leq n \leq 102, 1 \leq m \leq 100, 0 \leq k \leq 400,0 \leq r_i \leq 49, \forall 1 \leq i \leq k\) 。 (\(6 \%\))

第 \(2\) 組測資， \(0 \leq k \leq 400, 0 \leq r_i \leq 49, \forall 1 \leq i \leq k\) 。 (\(15 \%\))

第 \(3\) 組測資，無特別限制。 (\(79 \%\))

Sample Input 1

6 5 0
1 1 1 200000
200000 200000 1 200000
200000 1 1 200000
200000 1 200000 200000
200000 1 1 1

Sample Output 1

10

Sample Input 2

9 8 8
1 1 1 1 1 1 48763
1 1 1 1 1 1 1
48763 48763 1 1 1 48763 48763
48763 1 1 1 1 1 48763
48763 1 1 1 1 1 48763
48763 1 1 1 1 1 48763
48763 48763 1 48763 1 48763 48763
1 1 1 48763 1 1 1
2 2 0
3 2 0
4 2 0
5 2 0
6 2 0
7 2 0
8 2 0
5 5 1

Sample Output 2

21