Image Quilting (Small)

Image quilting builds a large image by stitching many copies of one pattern image together. Placing the copies side by side gives a poor result, because the edges that meet can differ a lot.

From the left: the source image, a plain side by side join, and an optimized join.

To get the smoother result of the third picture, use the method below. This problem only considers joining two grayscale images of the same height left to right.

The two images overlap and a natural boundary is chosen inside the overlap.

• Call the two images B1 and B2. B1 is on the left, B2 is on the right.
• Overlap the edges of the two images a little.
• Inside the overlap, choose the seam that makes the difference between B1 and B2 as small as possible. The seam and everything to its right is overwritten with the pixels of B2, which produces the new image.
  • The seam takes exactly one pixel from every row of the overlap.
  • The pixel chosen in one row cannot differ by more than one column from the pixel chosen in the row directly above or directly below it. In other words, two neighboring rows shift by at most one column.
  • In each row, the pixels left of the chosen pixel keep the color of B1, while the chosen pixel and the pixels to its right take the color of B2.

An example seam inside an overlap of 5 rows and 10 columns.

Many seams are possible, so you have to pick the one that joins the two images most naturally. The unnaturalness of a seam is the sum, over every pixel position on the seam, of the squared difference between the color value of B1 and the color value of B2. The most natural seam is the one with the smallest unnaturalness.

The B1 image and the B2 image of the overlap, together with the optimal seam.

Only grayscale images appear here, so every color value is an integer between 0 and 255. In the example above the seam of the third picture is optimal, and its unnaturalness is

$E = (79-62)^2 + (10-16)^2 + (130-120)^2 + (235-240)^2 = 450$

Given the color values of the overlap, write a program that computes the smallest unnaturalness among all seams you can choose.

The first line contains the height $H$ and the width $W$ of the overlap, separated by a space. ($1 \le H \le 10$, $1 \le W \le 10$) $H$ is the number of rows and $W$ is the number of columns. Only the color values of the overlap are given, and both images are $H$ rows by $W$ columns.

The next $H$ lines contain the color values of image B1. Each line is one row of the image and holds $W$ color values, integers between 0 and 255, separated by spaces. The order of rows and columns in the input matches the order of rows and columns in the image. The following $H$ lines contain the color values of image B2 in the same format.

Print the smallest unnaturalness among all seams you can choose, on one line.