Minimum Soldiers for Board Occupation

You are given an M × N chessboard. Some cells on the board are blocked (obstacles) and cannot be used. In the remaining (free) cells you may place soldiers, at most one per cell.

We say that a set of soldiers occupies the board if the following conditions are satisfied:

• For every row i (1 ≤ i ≤ M), there are at least \(L_i\) soldiers placed in that row.
• For every column j (1 ≤ j ≤ N), there are at least \(C_j\) soldiers placed in that column.

Your task is to choose some free cells on which to place soldiers (one soldier per cell) so that the board is occupied while using the minimum number of soldiers. Note that a soldier placed on cell \((i, j)\) counts toward both the \(i\)th row and the \(j\)th column.

Observation: Clearly, if the mandatory row and column requirements are \(L=[L_1, L_2, \ldots, L_M]\) and \(C=[C_1, C_2, \ldots, C_N]\), then at least \(T=\max\Big(\sum_{i=1}^{M}L_i,\;\sum_{j=1}^{N}C_j\Big)\) soldiers are needed. In this problem, you may assume that if each row has at least \(L_i\) free cells and each column has at least \(C_j\) free cells then an arrangement using exactly \(T\) soldiers exists.

If it is not possible to satisfy the requirements because some row or column does not have enough free cells, output -1.

inputFormat

The input begins with two integers M and N (1 ≤ M, N ≤ 1000) representing the number of rows and columns of the board.

Then follow M lines, each containing a string of length N. Each character is either . or #, where . denotes a free cell and # denotes an obstacle.

The next line contains M space‐separated integers, where the ith integer is \(L_i\) (0 ≤ \(L_i\) ≤ N).

The last line contains N space‐separated integers, where the jth integer is \(C_j\) (0 ≤ \(C_j\) ≤ M).

You may assume that 1 ≤ M×N ≤ 10⁶ and that the total number of free cells does not exceed M×N.

outputFormat

If it is possible to occupy the board, output a single integer — the minimum number of soldiers required. Otherwise, output -1.

sample

3 3
...
.#.
...
1 1 1
1 1 1

3