const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");

const [N, M] = input[0].split(" ").map(Number);
const grid = [];

for (let i = 1; i <= N; i++) {
  const line = input[i].split(" ").map(Number);
  grid.push(line);
}

// 두 칸의 거리 |r1-r2| + |c1-c2|
function getDistance(r1, c1, r2, c2) {
  const distance = Math.abs(r1 - r2) + Math.abs(c1 - c2);
  return distance;
}

function getCitySum(selectedChickens) {
  let citySum = 0;
  for (const house of houses) {
    let minForHouse = Infinity;

    for (const chicken of selectedChickens) {
      const dist = getDistance(chicken[0], chicken[1], house[0], house[1]);
      if (minForHouse > dist) {
        minForHouse = dist;
      }
    }
    citySum += minForHouse;
  }
  return citySum;
}
// 치킨집 grid 만들고, 방문의 경우 0으로 바꾸기
const chickens = [];
const houses = [];

for (let r = 0; r < N; r++) {
  for (let c = 0; c < N; c++) {
    if (grid[r][c] === 1) houses.push([r, c]);
    if (grid[r][c] === 2) chickens.push([r, c]);
  }
}

// 치킨집 M개 골랐을 때, 치킨거리 최소값을 출력
let totalMinDistance = Infinity;
const selectedStore = [];

function backtrack(start) {
  if (selectedStore.length === M) {
    const currentCitySum = getCitySum(selectedStore);
    if (totalMinDistance > currentCitySum) {
      totalMinDistance = currentCitySum;
    }
    return;
  }

  for (let c = start; c < chickens.length; c++) {
    selectedStore.push(chickens[c]);
    backtrack(c + 1);
    selectedStore.pop();
  }
}

backtrack(0);
console.log(totalMinDistance);

1. 치킨가게가 들어있는 배열에서 임의로 M개 선택
2. 선택한 가게들에 대해서 치킨거리 구하기
3. 치킨거리의 값이 최소인 경우 totalMinDistance 업데이트

백트랙킹의 원리

1. c = start: 중복과 순열 방지
   조합은 [A, B]와 [B, A]를 같은 것으로 봅니다.
   - 반복문이 항상 0부터 시작하지 않고 부모 함수로부터 전달받은 start 인덱스부터 시작하기 때문에, 이미 선택했던 요소보다 뒤에 있는 것들만 후보에 올립니다.
2. backtrack(c + 1): 다음 단계로의 전진
   현재 c번째 치킨집을 골랐다면, 다음 치킨집은 무조건 그다음 칸(c + 1)부터 찾아야 합니다.
   - 이 재귀 호출은 "방금 고른 거 말고 그 뒤에서 또 하나 골라와!"라는 명령과 같습니다.
   - 재귀가 깊어질수록(M에 가까워질수록) 선택된 요소들이 하나씩 쌓이게 됩니다.
3. selectedStore.pop(): 상태의 복구 (가장 중요)
   이 부분이 백트래킹의 꽃입니다. 특정 경로로 탐색을 마쳤다면(예: A, B를 고른 뒤), 다시 이전 상태로 돌아가야 다른 경로(예: A, C)를 탐색할 수 있습니다.
   - push로 들어갔다가 backtrack이 끝나고 나오면, 바로 pop을 실행하여 방금 넣었던 것을 빼냅니다.
   - 그래야 다음 루프에서 깨끗해진 공간에 다른 후보를 넣고 다시 재귀를 돌릴 수 있습니다.

[B,C] 탐색 로직

backtrack 로직 안에서 [B, C]를 탐색하게 되는 시점은 첫 번째 치킨집(A)을 선택한 모든 경우의 수가 끝난 직후

[B, C]가 탐색되는 실제 과정

• 치킨집이 A, B, C 세 개 있고 M=2일 때의 흐름

1. A를 포함한 탐색 (i=0):
   • selectedStore.push(A) 실행.
   • backtrack(1) 호출 → 여기서 [A, B], [A, C]를 다 찾습니다.
   • backtrack(1)이 종료되면 selectedStore.pop()이 실행되어 A가 빠집니다. (이제 selectedStore는 다시 빈 상태 [])
2. B를 시작으로 하는 탐색 (i=1):
   • 이제 부모 루프의 i가 1이 됩니다.
   • selectedStore.push(B) 실행. (현재 [B])
   • backtrack(2) 호출! (현재 i가 1이므로 i + 1인 2를 전달)
3. 드디어 [B, C] 완성:
   • backtrack(2) 안으로 들어오면, for 문은 c = 2부터 시작합니다.
   • selectedStore.push(C) 실행. (현재 [B, C])
   • selectedStore.length === M 조건에 걸려 [B, C] 시나리오의 거리 계산을 수행합니다.