题目描述
青青是一个学习很好的可爱的小孩。最近期中考刚结束,青青的班成绩不算太好。作为一名可爱的学习委员,青青决定组建几个学习小组来一起学习提高成绩。青青的班上有N个同学,每个同学都有一个语文成绩、数学成绩、英语成绩,为了更好的提高大家的学习成绩,青青决定将N个同学分成语文、数学、英语三个学习小组,并且为了使学习成绩好的同学尽可能不“扎堆”,他还要求语文小组语文最高的同学的成绩、数学小组数学最高同学的成绩、英语小组英语最高同学的成绩的和尽可能小。
更抽象的说,现在有N个元素,每个元素具有3个属性Ai, Bi, Ci,现在青青要求把全部元素分为3个集合,称为集合X、集合Y和集合Z,使表达式的值最小。
注意:可以让某个小组没有成员。
数据规模
对于10%的数据,1 ≤ n ≤ 5。
对于20%的数据,1 ≤ n ≤ 50。
对于30%的数据,1 ≤ n ≤ 100。
对于50%的数据,1 ≤ n ≤ 1, 000。
对于100%的数据,1 ≤ n ≤ 100, 000,1 ≤ Ai, Bi, Ci ≤ 100, 000, 000。
输入格式
第1行,一个整数N,表示有N个人。
第2行到第N+1行,三个整数Ai,Bi,Ci,表示第i个人语文、数学、英语的成绩。
输出格式
有一行,一个整数S,表示要求的最小值。
样例输入
样例输出