{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eZhuge Liang and Zhou Yu were famous strategists in The Three Kingdoms Period.\u003cbr\u003eDuring The War of the Red Cliff in which Cao Chao was defeated, they often sat together to play chess. But the chess they played was special.\u003cbr\u003eWe can call the chess \"Three Kingdom Chess\". There are 2 players, and each one has some soldiers. All the soldiers are put on an N × M chessboard. Each grid on the chess board can be mountain, plain or lake. And there are 3 kinds of soldiers which are footman, archer and rider. All kind of soldiers can stay at or pass through plains. None of them can stay at or pass through lakes. Only footmen and archers can stay at or pass through mountains.\u003cbr\u003eThere are at most K turns in the game. Two players take turns to act. The first turn is Zhuge Liang\u0027s turn, the second turn is Zhou Yu\u0027s, the third turn is Zhuge Liang\u0027s…and so on. When one player\u0027s soldiers are all destroyed or after the Kth turn, the game ends. In each turn, the player can move one of his soldiers to a destination and then let it attack one of the opponent\u0027s soldiers.\u003cbr\u003eThe rule of moving is as below. Every kind of soldiers has its \"pace length\". A soldier with \"pace length\" of q can move at most q steps(you can also let your soldier move 0 step). On each step, a soldier can move up, down, left or right by one grid. But please note that no soldier can pass a lake and a rider can\u0027t pass a mountain, as mentioned above. A soldier is also not able to pass a grid which is occupied by an enemy soldier. A soldier can pass, but cannot stay at a grid which is occupied by his comrade.\u003cbr\u003eAfter a soldier reaching his moving destination, he can launch an attack. A soldier can attack an enemy soldier who is in his \"attack region\". The attack regions of different kinds of soldiers are shown in the figures below:\u003cbr\u003e\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/ff4af37715ca3d3fb7e16ac3ba12d09d?v\u003d1726299052\"\u003e\u003c/center\u003e \u003cbr\u003e\u003cbr\u003eIt means that the soldier in the grid with a circle can attack one enemy soldier who is in the black grids.\u003cbr\u003eEvery soldier has a \"strength\" property. A soldier\u0027s strength will decrease if he is attacked. The strength decrement equals to S × F, which S is the attacker\u0027s strength, and F is the attacking factor. The attacking factor is 2 when a footman attacks an archer, an archer attacks a rider and a rider attacks a footman. It\u0027s 1 when a footman attacks a footman, a rider 6 attacks a rider and an archer attacks an archer. It\u0027s 0.5 when a footman attacks a rider, a rider attacks an archer and an archer attacks a footman.\u003cbr\u003eA soldier will be destroyed and disappear if its strengths is equal to or less than 0.\u003cbr\u003eIn one turn, a soldier can only launch one attack, and he can\u0027t move again in the same turn after attacking.\u003cbr\u003eAt the end, the score you get is the sum of strength of all your soldiers minus the sum of strengths of all your opponent\u0027s soldiers. So the score can be negative. Suppose Zhuge Liang and Zhou Yu were both very clever and always chose the best strategy to get as many score as possible, so what\u0027s the maximum score could Zhuge Liang get in the game?\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"There are several test cases. For each test case:\u003cbr\u003eThe first line contains 3 integers, N, M (1 \u0026lt;\u003d N, M \u0026lt;\u003d 5) and K (1 \u0026lt;\u003d K \u0026lt;\u003d 10), indicating that the chessboard is N × M, and the game will end after K turns.\u003cbr\u003eThen N lines follow, each containing M integers. Every integer represents a grid, showing the grid\u0027s property. 0 stands for plain, 1 stands for mountain and 2 stands for lake.\u003cbr\u003eThe next line contains 4 integers, T (1 \u0026lt;\u003d T \u0026lt;\u003d 6), S1, S2 and S3, indicating that there are T soldiers on the chessboard at the beginning. It is guaranteed that no more than one soldier stay at the same grid. S1, S2 and S3 mean the \"pace length\" of footman, rider and archer.\u003cbr\u003eFor the next T lines, each line contains 5 integers x, y, a, b and c, describing a soldier.\u003cbr\u003eThe soldier is in row x and column y (The coordinates x, y start from 1). If a\u003d0 then the soldier is Zhuge Liang\u0027s and if a\u003d1 then it is Zhouyu\u0027s. The strength of the soldier is b. c\u003d0 means the soldier is a footman, c\u003d1 means it is a rider and c\u003d2 means it is an archer.\u003cbr\u003eThe input ends with N \u003d M \u003d K \u003d 0."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output one line containing the maximumscore Zhuge Liang can get in the game."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 3 2\r\n0 0 0\r\n0 0 0\r\n0 0 0\r\n2 1 1 1\r\n2 1 0 100 0\r\n2 3 1 100 0\r\n0 0 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e100\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}