저격의 신이 되기 위해선 표적을 정확하게, 그리고 신속하게 제압하는 것이 중요하다. 다음 임무를 성공적으로 완료해 진정한 '저격의 신'이 되어보자.

$N \times M$ 크기의 목표 범위에 대해 $K$개의 표적이 있고, 당신은 이 $K$개의 표적을 모두 제압해야 한다. 지금 제압하고자 하는 표적의 좌표를 $(y_1, x_1)$, 다음으로 제압하고자 하는 표적의 좌표를 $(y_2, x_2)$라고 하자. 현재 표적을 제압한 후 다음 표적을 겨냥하기 위해서는 $(y_1, x_1)$에서 $(y_2, x_2)$에 도달하기 위해 발생하는 최소한의 좌표 변화 횟수만큼 시간이 걸린다. 좌표는 상, 하, 좌, 우로 $1$만큼 변화할 수 있다. 마지막 표적을 제압하고 나면 그 즉시 저격을 종료한다. 첫 표적에 있어선 좌표 변화 횟수를 $0$으로 한다.

$K$개의 표적을 제압하는 순서는 당신의 자유지만, 이 과정에서 발생한 좌표 변화 횟수의 총 합은 반드시 최소가 되어야 한다. 당신은 유능한 저격수이므로 표적을 제압하는 데에 걸리는 시간은 무시할 수 있으며, 본 문제에서는 오로지 좌표 변화 횟수만을 고려한다.

$N \times M$ 크기의 목표 범위 및 표적의 정보가 주어졌을 때, 모든 표적을 제압하기 위해 발생하는 좌표 변화 횟수의 최솟값을 구해보자.

첫째 줄에 목표 범위의 세로 길이 $N$과 가로 길이 $M$, 표적의 수 $K$가 공백으로 구분되어 주어진다. $(1 ≤ N, M ≤ 500; 1 ≤ K ≤ min(N \times M, 17))$

둘째 줄부터 $N$개의 줄에 걸쳐 목표 범위의 정보가 주어진다. '.'은 좌표 변화할 수 있는 빈 공간, '#'은 좌표 변화할 수 없는 벽, 'X'는 표적을 의미한다.

표적들이 벽에 의해 분리되는 경우는 입력으로 주어지지 않는다.