题目描述

喜逢太平盛世，女儿国国王希望自己的子民都喜结良缘，日夜祈求月老。月老感动，准备御花园中种下姻缘树，如能种成，则天下有情人均能眷属。 
御花园是一个环形的花园，月老想在花园周围均匀地种上n棵树，但是御花园的土壤很特别，每个位置适合种的树都不一样，一些树可能会因为不适合这个位置的土壤而损失观赏价值。
月老最喜欢4种树，这4种树的高度分别为20，30，50，70。月老希望这一圈树种得有层次感，所以任何一个位置的树要比它相邻的两棵树的高度都高或者都低，并且在此条件下，使得观赏价值之和最高。

输入格式：

输入第1行为一个正整数n，表示需要种的树的棵树。
接下来n行，每行4个不超过10000的正整数ai，bi，ci，di，按顺时针顺序表示了第i个位置种高度为20，30，50，70的树能获得的观赏价值。
第i个位置的树与第i+1个位置的树相邻，特别地，第1个位置的树与第n个位置的树相邻。

输出格式：

输出仅包括一个正整数，为最大的观赏价值和。

输入样例#1：

4
1 4 2 3
4 2 1 3
3 1 4 2
4 3 2 1

输出样例#1：

16

数据规模

对于 20% 的数据，有 n≤10；
对于 40% 的数据，有 n≤100；
对于 60% 的数据，有 n≤1000；
对于 100% 的数据，有 4≤n≤10^5 ，并保证 n 一定为偶数。