시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 70 39 36 54.545%

문제

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

존의 농장에는 작은 정사각형 목초지가 N×N (3 ≤ N ≤ 100) 격자로 이루어져 있다. 농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다. 이 농장에 사는 소 베시는 한 목초지에서 상하좌우로 인접한 다른 목초지로 이동할 수 있지만, 교통사고를 피하기 위해 차가 안 오는지 확인하고 길을 건너야 한다. 길을 건너는데는 T초 (0 ≤ T ≤ 1,000,000)가 걸린다.

존이 베시에게 체스 대결을 신청했다. 베시는 북서쪽 끝에 있는 목초지에서 남동쪽 끝에 있는 존의 집으로 가야 한다. 길이 멀기 때문에 베시는 가는 도중에 배가 고파진다. 그래서 길을 세 번 건널 때마다 목초지에 있는 풀을 먹어야 한다. 존의 집에 도착할 때도 마찬가지지만, 출발할 때는 해당되지 않는다. 목초지마다 풀이 자란 정도가 달라서, 풀을 먹는데 걸리는 시간도 다르다.

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

입력

첫 줄에 N과 T가 주어진다. 다음 N줄에는 목초지마다 풀을 먹는데 걸리는 시간이 N×N의 형태로 주어진다. 각각의 수는 모두 100,000 이하이다.

출력

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

예제 입력

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

예제 출력

31

힌트

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