10083 RGB거리 Silver I

문제

N개의 집이 일렬로 있다. 각 집을 빨강, 초록, 파랑 중 하나로 칠하는데, 인접한 집끼리는 같은 색으로 칠할 수 없다. 각 집을 각 색으로 칠하는 비용이 주어질 때, 모든 집을 칠하는 최소 비용을 구하시오.

입력

첫째 줄에 N (2 ≤ N ≤ 1,000)이 주어진다. 다음 N개의 줄에 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어진다. (1 ≤ 비용 ≤ 1,000)

출력

최소 비용을 출력한다.

3
26 40 83
49 60 57
13 89 99

96