Boss Monster Loot

In Memmem World, a boss monster is summoned at a random location at regular intervals.

The loot from this boss monster is so good that all players in Memmem World wait only for the summon notification. If a player lands even one hit, the loot is distributed in proportion to the damage dealt.

Given the current map of Memmem World, information about the players, and the boss monster's health, calculate the maximum number of players who can take the loot.

When the boss monster is summoned, every player moves to the boss monster's location by the fastest route, and starts attacking as soon as they arrive. An attack takes 1 second, and the attacks of all players at the same location as the boss happen simultaneously. A player can move up, down, left, and right, and each move takes 1 second. Multiple players can occupy the same point.

The first line of input gives two integers M (6 ≤ M ≤ 1000) and N (6 ≤ N ≤ 1000), the size of the map of Memmem World, and the number of players P (1 ≤ P ≤ 26). M is the height of the map and N is the width.

From the second line, M lines give the map. Here '.' is a passable path, 'X' is an impassable path, a lowercase letter is a player's id, and 'B' is the boss monster's location.

From the next line, P lines give a player's id and dps (1 ≤ dps ≤ 10000). An id is a lowercase English letter. dps means how much of the boss monster's health the player can reduce per second. The next line gives the boss monster's HP (10 ≤ HP ≤ 1000000). dps and HP are integers.

No input is given in which no player can go to catch the boss monster.

Output the maximum number of players who can take the loot.