You are given a board of $R$ rows and $C$ columns where each cell is either a dry land ('_#_') or an icy land ('_._'). You can move to either one of the four directions (north, south, east, or west) in the board.
You can walk or standstill on any dry land without any problem; however, an icy land is very slippery. If you stand at cell $(r, c)$ and decide to move on a particular direction, then you will move on that direction continuously until you reach a dry land or the border of the board.
For example, consider the following board of $6$ rows and $7$ column.
Supposed your initial position is at cell $(3, 7)$ and your moves are west, west, west, south, east, north, west, and west, respectively. Then your positions are $(3, 7)$ $arrow.r$ $(3, 4)$ $arrow.r$ $(3, 3)$ $arrow.r$ $(3, 1)$ $arrow.r$ $(6, 1)$ $arrow.r$ $(6, 2)$ $arrow.r$ $(2, 2)$ $arrow.r$ $(2, 1)$ $arrow.r$ $(2, 1)$, thus, visiting $8$ different cells. Note that cell $(2, 1)$ is visited twice. Cells in which you only passed through are also not considered as visited, e.g., in the example above, if you move south from $(3, 1)$, then you will pass through $(4, 1)$ and $(5, 1)$, and arrive at $(6, 1)$; thus, $(4, 1)$ and $(5, 1)$ are not considered as visited from that particular move, only $(3, 1)$ and $(6, 1)$ are.
You are allowed to change any icy land into a dry land, and your goal is to make sure that you can always visit *all* the cells in the board *regardless* of your initial starting position; in other words, you do not know your starting position yet, but given the board, you want to make sure that you can achieve your goal. What is the minimum number of cells you need to change to ensure that your goal can be achieved?
Input begins with a line containing two integers: $R$ $C$ ($1 <= R, C <= 500$) representing the number of rows and columns of the board, respectively. The next $R$ lines, each contains $C$ characters representing the given board. Each character is either '_#_' which represents a dry land or '_._' which represents an icy land.
Output contains an integer in a line representing the minimum number of cells you need to change to ensure that you can visit all the cells in the board regardless of your initial starting position.
_Explanation for the sample input/output_
We only need to change cell $(3, 3)$.
Let 'N' be north, 'S' be south, 'W' be west, and 'E' be east.
## Input
Input begins with a line containing two integers: $R$ $C$ ($1 <= R, C <= 500$) representing the number of rows and columns of the board, respectively. The next $R$ lines, each contains $C$ characters representing the given board. Each character is either '_#_' which represents a dry land or '_._' which represents an icy land.
## Output
Output contains an integer in a line representing the minimum number of cells you need to change to ensure that you can visit all the cells in the board regardless of your initial starting position.
[samples]
## Note
_Explanation for the sample input/output_We only need to change cell $(3, 3)$. .... .### ###. ###.Let 'N' be north, 'S' be south, 'W' be west, and 'E' be east. If you start at cell $(1, 1)$, then the movement "SSENNWENSESSEWNENWNE" will visit all the cells. The corresponding positions are: $(1, 1)$ $arrow.r$ $(3, 1)$ $arrow.r$ $(4, 1)$ $arrow.r$ $(4, 2)$ $arrow.r$ $(3, 2)$ $arrow.r$ $(2, 2)$ $arrow.r$ $(2, 1)$ $arrow.r$ $(2, 2)$ $arrow.r$ $(1, 2)$ $arrow.r$ $(2, 2)$ $arrow.r$ $(2, 3)$ $arrow.r$ $(3, 3)$ $arrow.r$ $(4, 3)$ $arrow.r$ $(4, 4)$ $arrow.r$ $(4, 3)$ $arrow.r$ $(3, 3)$ $arrow.r$ $(3, 4)$ $arrow.r$ $(2, 4)$ $arrow.r$ $(2, 3)$ $arrow.r$ $(1, 3)$ $arrow.r$ $(1, 4)$. If you start at cell $(1, 2)$, then the movement "W" followed by the movement in the first example above ("SSENNWENSESSEWNENWNE") will visit all the cells. The corresponding positions are: $(1, 2)$ $arrow.r$ $(1, 1)$ $arrow.r$ $\\dots$ If you start at cell $(1, 3)$, then the movement "W" followed by the movement in the first example above will visit all the cells. The corresponding positions are: $(1, 3)$ $arrow.r$ $(1, 1)$ $arrow.r$ $\\dots$ $\\\\cdots$ If you start at cell $(4, 3)$, then the movement "NNNW" followed by the movement in the first example above will visit all the cells. The corresponding positions are: $(4, 3)$ $arrow.r$ $(3, 3)$ $arrow.r$ $(2, 3)$ $arrow.r$ $(1, 3)$ $arrow.r$ $(1, 1)$ $arrow.r$ $\\dots$ If you start at cell $(4, 4)$, then the movement "NNW" followed by the movement in the first example above will visit all the cells. The corresponding positions are: $(4, 4)$ $arrow.r$ $(2, 4)$ $arrow.r$ $(1, 4)$ $arrow.r$ $(1, 1)$ $arrow.r$ $\\dots$
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ r, c \in \mathbb{Z} $ denote the number of rows and columns of the grid.
- Let $ B = (b_1, \dots, b_c) \in \mathbb{Z}_{\geq 0}^c $, where $ b_i $ is the number of balls dropped into column $ i $.
- Let $ S = (s_1, \dots, s_c) \in \mathbb{Z}_{\geq 0}^c $, where $ s_i $ is the score per ball in bucket $ i $.
- Let $ G = (g_{i,j})_{r \times c} $ be the initial grid, where each $ g_{i,j} \in \{ \text{.}, \backslash, / \} $.
Cells with $ g_{i,j} = \text{.} $ are fixed.
Cells with $ g_{i,j} \in \{ \backslash, / \} $ may be changed to any of $ \{ \text{.}, \backslash, / \} $.
**Constraints**
1. $ 1 \leq T \leq 5300 $
2. $ 1 \leq r, c \leq 500 $
3. $ \sum_{\text{test cases}} r \times c \leq 4 \times 10^6 $
4. $ 0 \leq b_i, s_i \leq 10^8 $
5. **No two adjacent cells in the same row may satisfy**: left cell is $ \backslash $ and right cell is $ / $.
**Objective**
Maximize total score:
$$
\sum_{j=1}^{c} s_j \cdot (\text{number of balls from column } j \text{ that reach bucket } j)
$$
by choosing, for each variable cell $ (i,j) $, a symbol in $ \{ \text{.}, \backslash, / \} $, such that:
- The path of each ball dropped in column $ j $ follows grid directions ($ \backslash $: down-right, $ / $: down-left, $ . $: down),
- No ball leaves the grid boundaries (i.e., if a ball moves left from column 1 or right from column $ c $, it scores 0),
- The adjacency constraint is satisfied: $ \forall i \in \{1,\dots,r\}, \forall j \in \{1,\dots,c-1\} $, it is not allowed that $ g_{i,j} = \backslash $ and $ g_{i,j+1} = / $.
Find the maximum achievable total score.