题目描述
有n个格子排成一排，每个格子可以设成红色、蓝色和绿色，不同的格子设成不同的颜色会获得不同的分值。两个相邻的格子不能设成相同的颜色，同一种颜色设在不同的格子可能得到不同的得分。求将n个格子设置成不同颜色后可以获得的最大得分。
输入
第一行，一个整数n(1<= n <= 1000)，代表格子的数目。 后面n行，每行3个数，代表第i个格子设置成红色、蓝色、绿色的得分，每次得分不超过100。
输出
一个整数数，最大得分。
样例输入
3
2 11 6
8 5 16
9 13 6样例输出
40