부스 카펫

한 박람회장의 복도에는 부스 N개가 1번부터 N번까지 한 줄로 늘어서 있다. 준비 팀은 부스마다 바닥에 카펫을 깔아야 한다. 카펫은 모래, 이끼, 바다 세 가지 색이 있고 한 부스에는 한 가지 색만 깐다.

같은 색이 나란히 놓이면 방문객이 부스의 경계를 알아보기 어렵다. 그래서 번호가 1만큼 차이 나는 두 부스에는 서로 다른 색의 카펫을 깔아야 한다. 번호가 2 이상 차이 나는 부스끼리는 색이 같아도 된다.

카펫을 깔 때 드는 비용은 색에 따라 다르고 부스에 따라서도 다르다. 준비 팀은 모든 부스에 카펫을 깔면서 전체 비용의 합을 가장 적게 하려고 한다.

각 부스에 세 가지 색의 카펫을 깔 때 드는 비용이 주어졌을 때, 전체 비용의 최솟값을 계산하는 프로그램을 작성하여라.

예를 들어 N=3인 상황을 가정하자. 각 부스에 색마다 드는 비용이 다음의 표와 같다고 해보자.

1번 부스에 바다, 2번 부스에 이끼, 3번 부스에 모래를 깔면 맞닿은 부스끼리 색이 모두 다르다. 이때의 비용을 정리하면 다음의 표와 같다.

각 부스에서 가장 싼 색만 고르면 1번은 바다, 2번은 이끼, 3번은 이끼가 되어 2번과 3번의 색이 같아지므로 조건에 맞지 않는다. 이처럼 부스마다 따로 싼 색을 고르는 방법으로는 답을 구할 수 없고, 앞 부스에서 고른 색이 뒤 부스의 선택을 묶는다는 점을 함께 보아야 한다. 조건을 지키면서 111보다 적게 드는 방법은 없으므로, 현재 예시에서의 정답은 111이다.

1번 부스와 3번 부스는 번호가 2만큼 차이 나므로 색이 같아도 된다. 예를 들어 바다, 이끼, 바다를 고르면 2 + 37 + 73 = 112가 되는데, 이 또한 조건을 만족하는 방법이지만 111보다 비싸다. 부스가 1개뿐인 경우에는 맞닿은 부스가 없으므로 세 가지 색 가운데 가장 싼 것을 고르면 된다.

입출력 예시

예시 1

입력

3
96 51 2
89 37 48
72 55 73

출력

111

예시 2

입력

5
68 62 38
34 21 22
12 52 81
13 74 42
14 31 93

출력

127

예시 3

입력

1
30 77 78

출력

30