Facer was addicted to a popular game called "Plants VS Zombies". After Facer had completed all missions, he started to play the zombies' role to destroy plants and called the new game "Zombies VS Plants".
In the game "Zombies VS Plants", there are 3 kinds of zombies: Little Zombie, Adult Zombie and Football player. Different zombies have different price and different "attacking value" indicating the capability to attack, as shown in the table below:
Zombie name | Attacking value | Price for one (in dollars) |
Little Zombie | 40 | 50 |
Adult Zombie | 70 | 75 |
Football player | 200 | 100 |
(1,1) | (1,2) | (1,3) | (1,4) | (1,5) |
(2,1) | (2,2) | (2,3) | (2,4) | (2,5) |
(3,1) | (3,2) | (3,3) | (3,4) | (3,5) |
(4,1) | (4,2) | (4,3) | (4,4) | (4,5) |
(5,1) | (5,2) | (5,3) | (5,4) | (5,5) |
Plant name | Defending value | Special features |
Sunflower | 0 | None |
Bean | 100 | None |
Magnet | 0 | A magnet can make the attacking value of the football players in the same row and the adjacent rows become 50. For example, if there is a magnet in row 3, the attacking value of all football players Facer put into row 2, 3 and 4 will become 50. |
Lettuce | 0 | Spiders can't destroy a lettuce and the plants in the eight cells around the lettuce. For example, if there is a lettuce at cell (3,3), spiders can't destroy the lettuce and the plants in (2,2), (2,3), (2,4), (3,2), (3,4), (4,2), (4,3) and (4,4). |
There are multiple test cases.
The first line in the input is a integer T indicating the number of test cases. (1 < T <= 400)
For each test case:
First line contains three integers P1, P2 and P3 (0 <= P1, P2, P3 <= 10000), meaning that Facer earns P1 dollars after destroying a row of plants and earns P2 dollars after destroying a sunflower, and Facer has P3 dollars at the beginning.
Following are 5 lines describing the plants field by top to bottom order. Each line contains 5 integers, telling what's in the cells of a row, by left to right order. For those 5 integers:
"1" represents a sunflower.
"2" represents a bean.
"3" represents a magnet.
"4" represents a lettuce.
For each test case, output one line containing an integer indicating the maximum amount of dollars Facer can keep after he accomplishes the mission. If Facer can't destroy all the plants, print '-1' instead.
2 100 100 10000 2 2 2 2 2 2 3 2 2 2 3 3 4 3 2 2 3 2 2 2 2 2 2 2 2 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
9025 -1