축제를 방해하는 아이들은 혼나야 해요!

아라타

선생님! 망량즈와 아라타가 신목제를 망치기 전에 저지해야 해요! 여기서 싸우면 폭죽에 불이 붙을 수도 있으니… 수행부 동아리 학생들의 도움을 받아 밧줄로 아라타를 포획하려고 해요.

광장은 $N \times N$ 격자예요. 저는 지금 $1$행 $1$열의 정중앙에 있고, 아라타는 광장 어딘가 한 칸의 정중앙에 있어요. 학생들의 도움을 받으면, 각 칸의 정중앙에서 정중앙으로 이동하면서 밧줄을 놓을 수 있을 것 같아요. 수행부 동아리 학생 이동은 인접한 상하좌우 칸으로만 가능해요.

수행부 동아리 학생들이 $1$행 $1$열에서 출발해 총 $K+1$개의 칸 $P_0$, $P_1$, $\cdots$, $P_K$를 차례대로 방문했다고 할게요.

• $P_0$는 시작점인 $1$행 $1$열이에요.
• $P_K$는 아라타가 있는 칸이에요.

이때 밧줄의 길이는 밧줄을 이루는 선분의 개수, 즉 $K$로 정의할게요.

아라타를 밧줄로 붙잡는 데 성공하면, 저는 즉시 밧줄을 잡아당겨서 회수해야 해요. 그런데 밧줄은 꺾인 부분이 많을수록 당길 때 더 걸리고 버벅여서 더 큰 힘이 필요해요. 힘이 많이 들면 회수가 늦어지고, 그 사이 아라타가 도망치거나 상황이 더 위험해질 수 있으니 총 힘도 최소화해야 해요.

현재 밧줄을 이루는 점이 $P_0$, $P_1$, $\cdots$, $P_i$일 때, 밧줄을 한 번 잡아당기면 다음과 같은 과정이 일어나요.

• 끝점 $P_i$가 제거되고, 남은 점 $P_0$, $P_1$, , 만이 밧줄을 이루어요.

저는 이 과정을 반복해서 밧줄을 끝까지 회수하고, 결국 점 $P_0$만 남을 때까지 잡아당겨야 해요.

망량즈가 무슨 짓을 하기 전에 최대한 빨리 아라타를 포획해야 해요. 그래서 아라타를 붙잡을 때 밧줄의 길이를 최소로 하고, 그러한 밧줄 중에서 제가 밧줄을 끝까지 회수하는 데 필요한 총 힘을 최소로 할 거에요. 이 두 값을 최소로 하기 위한 수행부 동아리 학생 이동 방법을 찾아야 해요. 선생님, 도와주시겠어요?

우미카는 반드시 $1$행 $1$열에만 존재하며, 아라타가 존재하는 칸은 정확히 하나이다.

항상 아라타를 잡는 것이 가능한 입력만 주어진다.

시간 제한

2000 ms

메모리 제한

256 MB

체커

CUSTOM