Making a Beautiful Puzzle

For his birthday Seongyong got an $N \times M$ puzzle board and $1 \times 1$ puzzle pieces in red, blue, green and yellow. He has infinitely many pieces of each color.

Seongyong puts exactly one piece on every square of the board. He wants the board to look colorful, so two squares that touch horizontally or vertically always hold pieces of different colors.

Putting a piece of a given color on a given square earns the beauty fixed in advance for that square and that color. The beauty of the whole puzzle is the sum of the beauty earned on every square.

Write a program that finds the largest possible beauty of the whole puzzle and the number of placements that reach it.

The first line contains $N$ and $M$, separated by a space. ($1 \le N \le 10$, $1 \le M \le 10$)

The next $N$ lines contain the beauty earned by putting a red piece on each square, $M$ values per line.

The following $N$ lines give the values for blue pieces, the next $N$ lines give the values for green pieces, and the last $N$ lines give the values for yellow pieces, in the same format.

Every beauty is an integer between $0$ and $10^9$. The largest possible beauty of the whole puzzle does not exceed 2,100,000,000.

On the first line print the largest possible beauty of the whole puzzle and the number of placements that reach it, separated by a space. The number of placements can be very large, so print it modulo $10^9 + 7$.

Write the four colors as R, B, G and Y.

In the first example the board has a single square, and every color gives a total beauty of 1, so 1 is the maximum. There are four placements.

In the second example, putting R and B on the top row and G and Y on the bottom row gives $2 + 2 + 2 + 2 = 8$, which is the maximum. Only one placement reaches it.