Pipes

Time limit1sMemory limit128 MB

Summary

Given a grid of modules with costs on interior walls, find the minimum-cost cycle that visits every module exactly once, starting and ending at the service module.

Level: Medium7 of 10
Topics: Dynamic programming, Bit manipulation, Matrix, Greedy
Solved: No attempts yet

Problem

Constructing office buildings has become a highly standardized task. Pre-fabricated modules are combined to fit the customer's needs, shipped from a distant factory, and assembled on site. Even so, a few tasks still demand careful planning — one of them is routing the pipes of the heating system.

A modern office building is made up of square modules. On each floor, exactly one of them is a service module, from which (among other things) hot water is pumped out to the remaining modules through the heating pipes. Every module — including the service module — is connected by heating pipes to exactly two of its two-to-four neighbouring modules. The pipes therefore form one closed circuit that leaves the service module, visits every module exactly once, and finally returns to the service module.

Because the modules differ, connecting a given pair of adjacent modules costs different amounts; a thick wall between two modules, for instance, raises the cost of laying pipe between them. Given the description of one floor, determine the cheapest way to route the heating pipes.

Input

The first line contains a single integer: the number of floors to process. Then follow that many floor descriptions.

Each description begins on a new line with two integers $2 \le r \le 10$ and $2 \le c \le 10$ — the floor measures $r$ rows by $c$ columns of modules. The next $2r + 1$ lines describe the floor in ASCII, each line holding $2c + 1$ characters.

In this layout the outer boundary is drawn with #, and the centre of every module is a space. Each interior wall separating two adjacent modules is a single digit 0–9, the cost of routing pipe through that wall. Every floor is perfectly rectangular and always contains an even number of modules.

Output

For each floor, print a single line containing the cost of the cheapest route.

Examples4

Example 1

Input

3
4 3
#######
# 2 3 #
#1#9#1#
# 2 3 #
#1#7#1#
# 5 3 #
#1#9#1#
# 2 3 #
#######
4 4
#########
# 2 3 3 #
#1#9#1#4#
# 2 3 6 #
#1#7#1#5#
# 5 3 1 #
#1#9#1#7#
# 2 3 0 #
#########
2 2
#####
# 1 #
#2#3#
# 4 #
#####

Expected output

28
45
10

Example 2
Input
```
1
2 2
#####
# 1 #
#2#3#
# 4 #
#####
```
Expected output
```
10
```

Example 3

Input

1
4 3
#######
# 2 3 #
#1#9#1#
# 2 3 #
#1#7#1#
# 5 3 #
#1#9#1#
# 2 3 #
#######

Expected output

Example 4
Input
```
1
2 2
#####
# 0 #
#5#0#
# 9 #
#####
```
Expected output
```
14
```