소가 길을 건너간 이유 7

소가 길을 건너는 이유는 그냥 길이 많아서이다. 존의 농장에는 길이 너무 많아서 길을 건너지 않고서는 거의 돌아다닐 수가 없다.

존의 농장은 작은 정사각형 목초지가 $N \times N$ ($3 \le N \le 100$) 격자 모양으로 모여 있다. 농장 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다. 이 농장에 사는 소 베시는 한 목초지에서 상하좌우로 인접한 다른 목초지로 이동할 수 있다. 하지만 교통사고를 피하려면 차가 오지 않는지 확인하고 길을 건너야 하므로, 인접한 목초지로 한 번 이동할 때마다 $T$초 ($0 \le T \le 1\,000\,000$)가 걸린다.

존이 베시에게 체스 대결을 신청했다. 베시는 북서쪽 끝(왼쪽 위) 목초지에서 출발해 남동쪽 끝(오른쪽 아래)에 있는 존의 집으로 가야 한다. 길이 멀어서 베시는 가는 도중에 배가 고파진다. 그래서 길을 세 번 건널 때마다, 세 번째로 건너서 도착한 목초지의 풀을 먹어야 한다. 이 규칙은 존의 집에 도착할 때도 적용되지만 출발할 때는 적용되지 않는다. 목초지마다 풀이 자란 정도가 달라서 풀을 먹는 데 걸리는 시간도 다르다. 베시는 같은 목초지를 여러 번 지나갈 수 있다.

베시가 존의 집에 가능한 한 빨리 도착하도록 도와주자.

첫째 줄에 $N$과 $T$가 주어진다. 다음 $N$개의 줄에는 각 목초지에서 풀을 먹는 데 걸리는 시간이 $N \times N$ 격자 형태로 주어진다. 첫 번째 줄의 첫 번째 수가 출발 목초지, 마지막 줄의 마지막 수가 존의 집이다. 각 수는 $0$ 이상 $100\,000$ 이하의 정수이다.

베시가 존의 집까지 가는 데 걸리는 최소 시간을 출력한다.

예제에서 30에서 출발해 가능한 한 빨리 도착하려면 10으로 간 뒤 풀을 먹고, 5로 간 뒤 풀을 먹고, 존의 집인 80으로 가야 한다. 길을 건너는 데 총 16초, 풀을 먹는 데 총 15초가 걸린다. 80에는 길을 두 번만 건너서 도착하므로 존의 집에서는 풀을 먹지 않는다.