이탈리아 베네치아의 부라노섬은 안개가 많이 끼는 특성 때문에 모든 집을 원색으로 칠한다. 이 때, 모든 이웃한 집은 같은 색으로 칠할 수 없다는 규칙도 있다. 이 마을에서 한 줄로 배치된 집들에 사는 사람들은 모두 빨강, 파랑, 초록 세 가지 색으로만 칠하기로 정하였다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 칠할 때  드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하여라.

입력

첫째 줄에 한 줄로 배치된 집의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용(1 이상 100 미만)이 주어진다.

출력

첫째 줄에 모든 집을 칠할 때 드는 비용의 최솟값을 출력한다. 단, 처음 집과 마지막 집은 이웃하는 집이 아니다.