Optimal Container Placement in a Warehouse Grid

You are given a warehouse represented by a 2D grid with dimensions \(m \times n\). Each cell in the grid is either empty (denoted by a '.') or blocked (denoted by a '#'). You also have a set of containers; each container occupies a consecutive sequence of grid cells and comes with a specified length. The goal is to place all the containers onto the grid using either a horizontal or vertical placement so that the containers do not overlap previously occupied cells.

The placement algorithm works greedily by first sorting the containers in descending order of their lengths. For each container, try to place it horizontally first. If a horizontal placement is not possible, then try to place it vertically. If neither placement works then it is impossible to place all containers and the answer for that test case is \(-1\). Otherwise, the answer is the sum of grid cells occupied by all containers.

Note: Once a container is placed in the grid, the occupied cells become blocked (i.e., they turn into '#' and cannot be used for subsequent placements).

inputFormat

The input is read from standard input (stdin) and consists of multiple test cases. Each test case is formatted as follows:

• The first line contains two integers \(m\) and \(n\) representing the dimensions of the grid.
• The next \(m\) lines each contain a string of \(n\) characters (each character is either '.' or '#') representing the grid.
• The next line contains an integer \(k\), the number of containers.
• The following \(k\) lines each contain one integer representing the length of a container.

The input terminates with a line containing a single 0.

outputFormat

For each test case, output a single line to standard output (stdout) containing one integer: the maximum number of used cells by optimally placing all containers, or \(-1\) if it is not possible to place all containers.

## sample

4 4
....
....
....
....
3
3
2
2
3 3
..#
.#.
..#
1
3
3 3
..#
.#.
..#
1
4
0

7
3
-1

</p>