Chicken Delivery

A city is an $N \times N$ grid. It is divided into cells of size $1 \times 1$, and each cell is an empty cell, a chicken restaurant, or a house. A cell is written as $(r, c)$, which means the $r$-th row from the top and the $c$-th column from the left. Both $r$ and $c$ start at 1.

The people who live in this city like chicken very much, so they often talk about the chicken distance. The chicken distance is the distance between a house and the chicken restaurant closest to it. It is defined with respect to a house, so each house has one chicken distance. The chicken distance of the city is the sum of the chicken distances of all houses.

The distance between two cells $(r_1, c_1)$ and $(r_2, c_2)$ is $|r_1 - r_2| + |c_1 - c_2|$.

For example, look at the city with the map below.

0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2

0 is an empty cell, 1 is a house, and 2 is a chicken restaurant.

The distance from the house at $(2, 1)$ to the chicken restaurant at $(1, 2)$ is $|2-1| + |1-2| = 2$, and the distance to the chicken restaurant at $(5, 5)$ is $|2-5| + |1-5| = 7$. The chicken distance of that house is 2.

The distance from the house at $(5, 4)$ to the chicken restaurant at $(1, 2)$ is $|5-1| + |4-2| = 6$, and the distance to the chicken restaurant at $(5, 5)$ is $|5-5| + |4-5| = 1$. The chicken distance of that house is 1.

Every chicken restaurant in this city belongs to the same franchise. The head office wants to close some of them to raise profit. After a long study it found that the number of chicken restaurants that earns the most profit in this city is at most $M$.

You must choose at most $M$ of the chicken restaurants in the city and close all the rest. Write a program that finds how small the chicken distance of the city can become.

The first line contains $N$ ($2 \le N \le 50$) and $M$ ($1 \le M \le 13$).

Each of the next $N$ lines describes one row of the city. A line contains $N$ numbers separated by spaces, where 0 is an empty cell, 1 is a house, and 2 is a chicken restaurant. The number of houses does not exceed $2N$, and there is at least 1 house. The number of chicken restaurants is at least $M$ and at most 13.

Print on the first line the minimum chicken distance of the city when at most $M$ chicken restaurants are kept open.