题目描述

假如有一排房子，共 n 栋，每栋房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。

例如，costs[1][0] 表示第 1 号房子粉刷成红色的成本花费；costs[2][2] 表示第 2 号房子粉刷成绿色的花费，以此类推。

请计算出粉刷完所有房子最少的花费成本。

输入格式

输入共 n + 1 行。第 1 行包含一个正整数 n。 第 2 行第 n + 1 行，每行包含三个整数 ，表示编号为 i 的房子被粉刷成红色、蓝色或者绿色需要的花费。

输出格式

仅一行，1个整数，表示字粉刷完所有房子最少的花费成本。

样例1

1
7 6 2

2

样例2

3
17 2 17
16 16 5 
14 3 19

10

数据范围

1 ≤ n ≤ 10000； 1 ≤ costs[i][j] ≤ 10000。