Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3695
Plants vs Fat Sheeps

Time Limit: 2 Seconds      Memory Limit: 65536 KB

A huge wave of fat sheeps is coming!

This time, plants have travelled to planet 218. They have heard the fat sheeps here had won the A-level Chinese Meals championship in Universe Final. Certainly they won't miss the chance to taste this meal! Now, all what they need to do is to lay an ambush for those tasty sheeps...

But before laying an ambush, we need to know the environment here clearly. You can assume that planet 218 is a rectangle containing N*M grids. Grids may have different terrains.

Here are four kinds of terrains, including:

  • 1. Plains. Sheeps can pass 1 plain in 1 minute.
  • 2. Stones. It can be seen as obstacles. Sheeps won't pass stones.
  • 3. Knolls. Sheeps won't pass knolls either. But it's a wonderful place for plants to thrive safely. Plants will and only will grow in knolls. 1 knoll can grow 1 plant, and once grown, plants can't be moved.
  • 4. Wetland. It cost sheeps 2 minutes to pass 1 wetland.

Here are two kinds of plants that can cook sheeps, including:

  • 1. Fire Pea. It can hit all sheeps in an horizontal or vertical line while its pea flies by before it hit stones or knolls. It can be planted facing 4 directions (up, down, left, and right), but you can't change directions once grown.
  • 2. Fume-shroom. It will let out hot gases filling all surrounding grids whose Manhattan distances to it are equal to or less than X. For two grids (x1, y1), (x2, y2), the Manhattan distance is |x1 - x2| + |y1 - y2|.

And now all plants can be upgraded! Each plant has a basic energy cost Ri, a basic attacking speed Si (which means plant i can attack Si times in a minute), a basic damage Ti on level 1. If a plant spend Ui more energy, it upgrades a level, and it will receive Vi bonus attacking speed and Wi bonus damage each level. Certainly, it has a max level Li (the initial level is level 1).

Now, P sheeps is coming. Each sheep will occupy 1 grid and have Hi hit points (HP). Each sheep will appear at minute Gi, and if two sheeps are standing on the same grid, they will be attacked simultaneously. Only when a sheep's HP is lower or equal to 0 will it be cooked. And, They will just run in the shortest path (which means, the time cost is minimal) towards the end without any pause or retreat. If there exist more than 1 shortest path, choose the one with the minimal alphabet order, if we express the path with N,S,E,W (N for North, S for South, E for East, W for West).

The whole planet has 1 start and 1 exit on different grids to sheeps' home only, and the terrain of the start and the exit will always be a plain. Sheeps will spend 1 minute on the start and exit as well. There will be at least 1 path between the start and the end. Plants can grow in an instant at any time.

Plants want to know the minimal energy it will cost to cook all sheeps. Will any fat sheeps avoid this doom?

Input

The input contains less than 30 test cases.

The first line contains two integer N, M, P (1 ≤ N, M ≤ 32 , 1 ≤ P ≤ 1024). Following N lines contain M characters each, indicating the map, with '.' stands for plains, 'x' stands for stones, 'k' stands for knolls, and 'w' stands for wetlands. Specially, 's' stands for start, and 't' stands for the exit. Next line include P integers Hi (1 ≤ Hi ≤ 1024), indicating the HP of each sheep. Next line include P integers Gi (0 ≤ Gi ≤ 1024), indicating the appearing time of each sheep. Following a line contains the R1, S1 ,T1 ,U1 ,V1 ,W1 ,L1 (1 ≤ R1, U1 ≤ 100, 0≤ S1, T1, V1, W1 ≤ 100, 1 ≤ L1 ≤ 5) of Fire Pea. Following a line contains the R2, S2 ,T2 ,U2 ,V2 ,W2 ,L2, X (1 ≤ R2, U2 ≤ 100, 0≤ S2, T2, V2, W2 ≤ 100, 1 ≤ L2 ≤ 5, 1 ≤ X ≤ 5) of Fume-shroom.

Output

For each test case, output a line with an integer, indicating the minimal cost if plants can cook all sheeps. If not, output "Happy summer holiday!".

Sample Input

4 5 1
.wwx.
s....
.kkw.
....t
5
0
4 1 4 3 1 1 2
5 1 0 1 1 1 2 2
3 3 4
wxk
swx
.tw
1 2 3 4
1 2 3 4
1 5 5 1 5 5 5
1 5 5 1 5 5 5 1

Sample Output

6
Happy summer holiday!

Hint

In case 1, the route is "EEEESS", because it only takes 7 minutes, and compared to "SSEEEE", it has the minimal alphabet order. You can plant an level 2 Fume-shroom on any grid of knolls. That plant's speed is 2 and damage is 1. It can cook the sheep when the sheep walks around it for 3 minutes. It cost 6 energy.

In case 2, none of the plants can hit sheeps.


Author: LIN, Jinghao
Contest: ZOJ Monthly, March 2013
Submit    Status