409985: GYM103886 L Fossil Excavation

The advance of space exploration led to the discovery that not only do ancient aliens on Mars exist, they used to eat cereal too!

Mythreya, an aspiring paleontologist, has gone to Mars to excavate all the alien fossils and artifacts. Mythreya and the CerealCodes team need to quickly extract the $$$k$$$ fossils from the excavation site, which can be described as an $$$n \times n$$$ grid. Each individual cell has coordinates $$$(x,y)$$$, $$$(1 \le x,y \le n)$$$ where $$$x$$$ means that the cell is in the $$$x$$$-th row and $$$y$$$ means that the cell is in the $$$y$$$-th column.

They must bring all $$$k$$$ fossils to the base, located at cell $$$(1,1)$$$. Also, because they are on Mars, they will be traversing the rocky planet using their Rover for Terrestrial Exploration (RTE), which runs on fuel.

The grid itself contains only three different kinds of characters:

'.' signifying an empty space. It takes $$$0$$$ fuel to traverse this cell. The base will always be an empty space.

'+' signifying a rocky path. It takes $$$1$$$ fuel to traverse this cell.

'#' signifying a giant boulder. It is not possible to traverse this cell. Fossils will not be located on boulders.

The rover can move to any neighboring cell so long as it is not a boulder or outside of the grid. The fossils themselves are incredibly heavy; the $$$i$$$-th fossil weighs $$$w_i$$$ kilograms.

As such, the CerealCodes team has crafted a giant, super high-tech wheelbarrow to carry the bones around for them.

The wheelbarrow can carry at most $$$m$$$ kilograms at a time. The fossils must remain intact, so they can't be taken apart into smaller pieces.

However, because it is a high-tech wheelbarrow, new fossils can be placed into it instantaneously. After the wheelbarrow is brought to the base, all the fossils in it can instantaneously be removed as well(multiple trips to the base may be required to deposit fossils since the wheelbarrow may not be sturdy enough to carry them all at once).

Help Mythreya and the CerealCodes team figure out the minimum amount of fuel it will take to bring all fossils to the the base, if they are all currently located at the base!

The first line of input contains four integers, $$$n$$$, $$$k$$$, and $$$m$$$ $$$(2 \le n \le 500, 1 \le k \le 12, 1 \le m \le 10^9)$$$.

The next $$$n$$$ lines represent the excavation site. Each line will have $$$n$$$ characters.

Finally, the next $$$k$$$ lines contain information on the fossils themselves. The $$$i$$$-th of these $$$k$$$ lines will consist of three numbers, $$$x_i$$$, $$$y_i$$$, and $$$w_i$$$ $$$(1 \le x_i,y_i \le n, 1 \le w_i \le m)$$$. It is guaranteed that all fossils will be reachable from the base.

Output the answer as an integer on a single line.

10 4 7
....##+.+.
###.+.+++.
###....+..
++....####
....######
.+..######
.+....++++
#...++.###
###+++###.
####.+####
7 1 2
3 9 5
10 5 6
1 10 1

6

In the sample case, it is optimal to first place fossils $$$2$$$ and $$$4$$$ into the high-tech wheelbarrow and bring them to the base. Then, one can bring the other two fossils to the base in any order. Mythreya and the CerealCodes team will have to traverse rocky cells at least $$$6$$$ times, so the answer is $$$6$$$. It can be shown that there is no better answer.

Problem Credits: Patrick Deng and Eric Hsu