승우는 충남대학교 캠퍼스를 가로질러 현성이의 사무실로 가려고 한다. 캠퍼스는 $N \times N$ ($3 \le N \le 100$) 크기의 격자 모양 구역들로 이루어져 있다. 캠퍼스의 내부에는 구역들을 구분하는 $N-1$개의 남북 방향 도로와 $N-1$개의 동서 방향 도로가 있다. 캠퍼스의 외곽에는 울타리가 둘러져 있어 승우가 캠퍼스 밖으로 나가는 것은 불가능하다.

승우는 인접한 구역(상, 하, 좌, 우)으로 자유롭게 이동할 수 있지만, 구역 사이의 도로를 건널 때마다 차가 오는지 주의 깊게 살펴봐야 한다. 도로를 한 번 건너는 데는 $T$ ($0 \le T \le 1\,000\,000$)만큼의 시간이 걸린다.

승우는 캠퍼스의 가장 왼쪽 위 칸에서 출발하여 가장 오른쪽 아래 칸에 있는 현성이의 사무실로 가야 한다. 승우는 가는 길에 배가 고프기 때문에, 방문하는 구역 3개마다(이동 3번마다) 멈춰서 간식을 먹는다. 이때 출발하는 칸은 횟수에 포함하지 않지만, 마지막 도착 지점이 3번째 방문하는 칸이라면 간식을 먹어야 한다. 각 구역은 간식의 맛이 다르기 때문에 멈춰서 간식을 먹는 데 걸리는 시간도 구역마다 다르다.

승우가 현성이의 사무실에 도착하는 데 걸리는 최소 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 $N$과 $T$가 공백으로 구분되어 주어진다. ($3 \le N \le 100$; $0 \le T \le 1\,000\,000$)

이어서 $N$개의 줄에 걸쳐 각 구역에서 간식을 먹는 데 걸리는 시간을 나타내는 $N$개의 양의 정수가 공백으로 구분되어 주어진다. 각 정수는 $100\,000$ 이하이다. 입력의 두 번째 줄부터 주어지는 행렬의 첫 번째 숫자는 가장 왼쪽 위 칸의 정보다.

출력

승우가 현성이의 사무실에 도착하는 데 걸리는 최소 시간을 출력한다.

예제 입력 1

4 2
30 92 36 10
38 85 60 16
41 13 5 68
20 97 13 80

예제 출력 1

31