C. Cubism
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Magikarp is trying out a new technique called Cubism. With a carefully arranged set of blocks, he can create three different images when viewed from different angles!

Magikarp has a grid of $$$n\times m\times k$$$ positions, measured along the $$$x$$$-, $$$y$$$-, and $$$z$$$-axes, respectively. Each position $$$(x,y,z)$$$, where $$$1\le x\le n$$$, $$$1\le y\le m$$$, and $$$1\le z\le k$$$, can contain at most one unit cube. Cubes may float freely and do not need to be connected.

When standing in front of the sculpture, $$$+x$$$ points to your right, $$$+y$$$ points forward into the sculpture, and $$$+z$$$ points upward. Each view is an orthogonal projection: its lines of sight are parallel to its viewing direction.

He has already chosen three images for his artwork:

  • The top view looks in the $$$-z$$$ direction, with $$$+x$$$ to the right and $$$+y$$$ upward in the image. It has $$$m$$$ rows and $$$n$$$ columns.
  • The front view looks in the $$$+y$$$ direction, with $$$+x$$$ to the right and $$$+z$$$ upward in the image. It has $$$k$$$ rows and $$$n$$$ columns.
  • The right view looks in the $$$-x$$$ direction, with $$$+y$$$ to the right and $$$+z$$$ upward in the image. It has $$$k$$$ rows and $$$m$$$ columns.

An entry is # if at least one cube exists along its line of sight, and . if no cube exists along that line.

Find the maximum number of cubes Magikarp can place so that all three views match his chosen images exactly. If no such arrangement exists, output -1.

Input

The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1\le n,m,k\le 300$$$) — the numbers of positions along the $$$x$$$-, $$$y$$$-, and $$$z$$$-axes, respectively.

The next $$$m$$$ lines each contain a string of $$$n$$$ characters — the top view.

The next $$$k$$$ lines each contain a string of $$$n$$$ characters — the front view.

The next $$$k$$$ lines each contain a string of $$$m$$$ characters — the right view.

Each character is either # or .. Each image is given row by row from top to bottom, with each row written from left to right, using the orientations defined above.

Output

Output a single integer — the maximum number of cubes in an arrangement matching all three views, or -1 if no such arrangement exists.

Examples
Input
2 2 2
##
##
##
##
##
##
Output
8
Input
15 5 5
###..#..##..##.
#...#.#.#.#.#.#
#...###.##..##.
#...#.#.#.#.#..
###.#.#.#.#.#..
#.#..#..##..##.
#.#.#.#.#.#.#.#
##..###.##..##.
#.#.#.#.#.#.#..
#.#.#.#.#.#.#..
#####
#####
#####
#####
#####
Output
139
Input
3 3 3
.##
##.
#.#
.#.
.##
#.#
..#
##.
.##
Output
-1
Note

In the first sample, all eight positions can contain cubes.

In the second sample, the front and top views spell "KARP" and "CARP", respectively. A maximum of $$$139$$$ cube positions can be filled.

Second sample: front view ("KARP"). Second sample: top view ("CARP"). Second sample: filled right view.
Close-up of the sculpture in the second sample, or see a video here.

In the third sample, the top view requires a cube with $$$x=1$$$ and $$$y=1$$$. The front view allows such a cube only at $$$z=1$$$, but the right view forbids a cube with $$$y=1$$$ and $$$z=1$$$. Therefore, no arrangement exists.