#000285

BubbleBugsBunny

Elmer Fudd’s farm, way north of here, is well known for having the best carrots in the whole area. Elmer spends most of his time working on his farm and he would not be pleased even if someone just stepped into it.


One day, Bugs Bunny and his bunny friends wanted to have a snack. Actually, there were not as hungry as much as they wanted to mess with Elmer. They went on his farm to eat as many carrots as they could. What they did not know was that Elmer set a trap! The ground around the bunnies suddenly collapsed and each of them was left standing on a fragile looking pillar while the fire begun to rage below… and you could see Elmer running with his gun…


Help Bugs Bunny and his friends! Get as many bunnies as possible out of the farm, and report the number of casualties.


The pillars on the farm are aligned in a grid with each pillar one unit away from the pillars to its east, west, north and south. Pillars at the edge of the farm grid are one unit away from safety, because as long as the bunnies are outside of the farm, they can hide so Elmer cannot shoot them anymore. Not all pillars necessarily have a bunny. A bunny is able to jump onto any unoccupied pillar that is within d units of his current one (Euclidian distance between those two pillars has to be less than or equal to d). A bunny standing on a pillar within jumping distance of the edge of the farm may always jump to safety, but there is a catch… Each pillar becomes weakened after each jump, and will soon collapse and no longer be usable by other bunnies. Jumping onto a pillar does not cause it to weaken, only jumping off of it causes it to weaken and eventually collapse. Only one bunny can be on one pillar at any given moment.


InputInput begins with a line containing a single positive integer n representing the number of rows in the map of the farm, followed by a single non-negative integer d representing the maximum jumping distance for the bunnies. Two maps follow, each as a map of characters with one row per line. The first map will contain a digit [0-3] in each position representing the number of jumps the pillar in that position will sustain before collapsing (0 means there is no pillar there). The second map will follow, with a 'B' for every position where a bunny is on the field and a '.' for every empty field. There will never be a bunny on a position where there is no pillar.
Each input map is guaranteed to be a rectangle of size nm, where 1 ≤ n ≤ 20 and 1 ≤ m ≤ 20.
Jumping distance is guaranteed to be in the range 1 ≤ d ≤ 4.

OutputYou should output a single line, containing the number of bunnies that could not escape.


Input:
3 1
1111
1111
1111
BBBB
BBBB
BBB

Output:
2

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.