```
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
board = []
houses = []
chickens = []
for n in range(N):
line = list(map(int,input().split()))
board.append(line)
for m in range(N):
if line[m]==1:
houses.append([n,m])
if line[m]==2:
chickens.append([0,n,m])
def check_dist():
# BFS
result = 0
remains = [chickens[i] for i in range(len(chickens)) if remain_chickens[i]==1]
for x,y in houses:
dist = int(1e4)
for _,r,c in remains:
dist = min(dist, abs(r-x)+abs(c-y))
result += dist
return result
answer = int(1e4)
remain_chickens = [1 for _ in range(len(chickens))]
def dfs(nums, idx):
global answer, remain_chickens
if nums == 0:
dist = check_dist()
if answer > dist:
answer = dist
else:
for i in range(idx,len(chickens)-nums+1):
remain_chickens[i] = 0
dfs(nums-1,i+1)
remain_chickens[i] = 1
dfs(len(chickens)-M ,0)
print(answer)
```