A river flows from north to south. You want to harness the river's waters to generate hydroelectricity to keep up with the increasing power demands of your state. 

You want to build a hydroelectric power plant in the bottom-right cell. However, to ensure that construction is efficient, you need to stop the river water from coming into that cell. To facilitate this, you decide to build a dam on the river based on the way it flows. You may only build a dam in any cell that is not a rock.

The river water has a natural current (direction of flow). It starts flowing from the top-left cell, and through any cell, it only flows either to the right or to the bottom.

A snap-shot of the flow of river water is shown as an example below:

The natural flow of this river can be modeled using a flow model in the form of a grid.

...##
.#.##
.....
##.#.
##...

This is what the symbols in the flow model mean:

• Dot (.) symbols: Represent spaces from where the river can flow
• Hashtag (#) symbols: Represent rocks and the river does not flow through these

Using the flow model, you may build a dam (marked as D) only in three cells as shown below to prevent water from entering the bottom-right cell:

D..##
.#.##
..D..
##.#.
##..D

If you build the dam in the center (as shown in the grid below), the flow of river water to the bottom-right cell is stopped:

...##
.#.##
..D..
##.#.
##...

A snap-shot of the building of a dam at the center is shown below:

However, if you build the dam in any other cell other than the cell in the center, it will not stop the water from entering the bottom-right cell. For example, if you build the dam as follows, the water will still reach the bottom-right cell because at least one path still exists from the top-left cell to the bottom-right cell.

...##
.#D##
.....
##.#.
##...

Task

To build the dam in cell (i, j), you need to spend cost(i, j) units of money. Your task to build the dam by spending the least amount of money.

Determine the minimum cost required to build exactly one dam based on the given river model such that you can stop the river water from entering the bottom-right cell. 

Example

Assumptions

• N = 4
• M = 4
• flow = [[..##], [...#], [#...], [##..]]
• cost = [[4 6 5 3], [5 2 5 1], [5 5 3 9], [9 5 5 4]]

Approach

You may build a dam on any of the cells that are marked with D below:

D.##

.D.#

#.D.

##.D

The cheapest cell out of these is the cell, which has the cost of building the dam is 2. And thus, that is the answer to the problem.

Function description

Complete the buildDam function provided in the editor. This function takes the following 4 parameters and returns the minimum cost to build a dam;

• N: Represents an integer denoting rows of river model
• M: Represents an integer denoting columns of river model
• flow: Represents a string array describing the river model
• cost: Represents a 2D integer array denoting the cost of building a dam

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

• The first line contains a single integer N denoting the rows in the river model.
• The second line contains a single integer M denoting the number of columns in the river model.
• N lines follow, where each line contains a single string of Dots (.) and hashes(#) – describing the river model.
• The next line contains a 2D grid of order N x M, where the cell (i, j) of this grid will tell you the cost associated with building a dam at cell (i, j)

Output format

Print a single line containing a single integer representing the minimum cost to build a dam on some valid cell.

Constraints

$1 \le N \le 10^3 \\ 1 \le M \le 10^3 \\1 \le cost_{ij}\le 10^9$

Note: It is guaranteed that at least one path exists for the river to go from the top-left to the bottom-right cell.

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.