#include #include using namespace std; int n; int mat[21][3]; int dp[21][4][4]; int rek(int at, int prev, int last){ if(at == 0){ if(prev == last)return mat[0][prev]; return (1 << 30); } if(dp[at][prev][last] != -1){ return dp[at][prev][last]; } int ret = (1 << 30); if(prev == 0){ ret = min(ret, rek(at - 1, 1, last) + mat[at][0]); ret = min(ret, rek(at - 1, 2, last) + mat[at][0]); } else if(prev == 1){ ret = min(ret, rek(at - 1, 0, last) + mat[at][1]); ret = min(ret, rek(at - 1, 2, last) + mat[at][1]); } else if(prev == 2){ ret = min(ret, rek(at - 1, 0, last) + mat[at][2]); ret = min(ret, rek(at - 1, 1, last) + mat[at][2]); } return dp[at][prev][last] = ret; } int main(int argc, const char * argv[]) { ios_base::sync_with_stdio(false); cin >> n; int a, b, c; for(int i = 0; i < n; i ++){ cin >> a >> b >> c; mat[i][0] = a; mat[i][1] = b; mat[i][2] = c; } memset(dp, -1, sizeof dp); int ret = (1 << 30); for(int i =0; i < 3; i ++){ for(int j=0 ; j <3; j ++){ if(i != j) ret = min(ret, rek(n - 1, i, j)); } } cout << ret << endl; return 0; }