Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

Language:
The story of three kingdoms XI
 Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 487 Accepted: 51

Description

Recently, Facer is absorbed in playing “The story of three kingdoms XI”. It is an interesting game but the battle system is so complicated and it always cost much time. In order to fasten the game process, Facer decide to write a auto-play program.

It's Facer's turn. Now Facer can control his troops one by one (in any order) and he wants to eliminate as many enemies as possible in his round. The battlefield is a matrix of N*M grids (1≤ N,M≤ 10) and each grid can be either grass field (represented as 'O') or mountain (represented as 'X'). Only grass fields might be occupied by Facer's troops or enemies', but each grid can be occupied by ONLY ONE troop. Each of Facer's troops can take an action of "MOVE once and ATTACK once"----which means first move the troops to a target area and then attack an adjacent enemy troop. Note that the action of "attack first and then move” is not allowed, but "No move but attack" , " move and no attack" and “ No move or attack” are all legal.

There are three kinds of troops----Lancers, Halberdiers and Cavaliers. Each kind of troops has an Ability of Movement (AM) and an Ability of Attacking (AA). AM decides how far the troops can go and AA decides the damage of one soldier in the troops.

In the process of MOVE, Facer's troops can move up to AM times to adjacent grids in up/left/right/down directions. Troops can go through other Facer's army (considered as non-occupied-grass field) but enemies will block the way (considered as mountains). For example, if Troops A has an AM of 3 then move to any of the BOLD field is legal. (Where F regard as enemy troops and B is one of Facer's army).

X O F O X
X X O A X
O O B O X
X O X X X

In the process of ATTACK, Facer's troops can deal some damage to adjacent enemy troops (adjacent in four directions in up/left/right/down). The basic damage equals to number of soldiers in the troops multiply AA of that kind of troops. When use Lancers to attack Cavaliers (represented as Lancers->Cavaliers), the damage will be doubled. This will also happen when Cavaliers->Halberdiers and Halberdiers->Lancers. Enemy troops will lost the same number of soldiers as the final damage point. Note that if the damage point is higher than the rest number of soldiers, the exceeded damage will be wasted.

To simplify the question, even if all the soldiers of an enemy troops are lost, the grid is still considered occupied and Facer's troops cannot go through.

Now given the information of the battlefield and write a program to decide how many enemy soldiers can be eliminated in Facer's turn.

Input

There are multiple test cases.For each test case,

The first line contains three integers representing the AM of Lancers, AM of Cavaliers and AM of Halberdiers.

The second line contains three integers representing the AA of Lancers, AA of Cavaliers and AA of Halberdiers.

The third line contains two integers representing N and M, the size of battlefields.

The following N lines describe the battlefields. Each line contains M element.

Each element could be:

'O'- Non-occupied-Grass field

'X'- Mountains

A character in 'A'-'F' and an integer-Occupied grass field ('A' for Facer's Lancers, 'B' for Facer's Cavaliers, 'C' for Facer's Halberdiers, 'D' for Enemy Lancers, 'E' for Enemy Cavaliers, 'F' for Enemy Halberdiers, the integer stands for the number of soldiers in that troops and the integer will be in the range of 1 to 100)

A test case starting with three zeros indicates the end of input data.

Note that both Facer and his enemy will have up to 10 troops.

Output

For each test case, output contains only one integer, the maximum number of enemy soldiers Facer can eliminate in his turn.

Sample Input

```3 3 3
1 1 1
4 4
X A1 A1 X
X O O X
X D1 D1 X
X X X X
0 0 0
```

Sample Output

`2`

Source

[Submit]   [Go Back]   [Status]   [Discuss]