17491번 - 고양이 밥주기 서브태스크채점 준비 중

윤성이는 건대에서 둘째가라면 서러워할 캣맘이지만, 자신이 캣맘이라는 사실을 부끄러워한다. 사실 누구보다 고양이를 좋아하면서 왜 본심을 숨기는 걸까?

윤성이는 교내 고양이들에게 밥을 준다는 사실을 아무에게도 들키고 싶지 않기 때문에, 최대한 짧은 경로로 모든 고양이들에게 밥을 주고 돌아가고 싶어한다.

학교는 2차원 평면으로 나타낼 수 있고, 윤성이는 상하좌우로 1칸씩 이동 가능하며 1칸 이동할 때 마다 1초씩 걸린다. 고양이가 위치한 좌표까지 이동해야 밥을 줄 수 있으며 윤성이는 시크해서 밥만 주고 떠나기 때문에 고양이에게 밥을 주는 시간은 소요되지 않는다.

윤성이는 학교에 하나밖에 없는 교문에 서있고 교문의 좌표는 (0,0) 이다. 모든 고양이에게 밥을 주고 난 뒤에는 다시 이 교문으로 돌아와야 한다.

윤성이는 최소 몇 초 만에 모든 고양이에게 밥을 주고 떠날 수 있을까?

첫 줄에 고양이의 수 N (1 ≤ N ≤ 16)이 주어진다. 다음 N 개의 줄에 고양이의 위치 좌표 X , Y 가 공백으로 구분되어 주어진다. (0 ≤ X, Y ≤ 1,000,000)

(0,0)에서 시작해서 모든 고양이에게 밥을 주고 다시 (0,0)으로 돌아오는 동안 걸린 시간(초 단위)을 첫 줄에 출력한다.

• 1 ≤ N ≤ 8

• 추가 제한 조건은 없다.