“今日云骈渡鹊桥,应非脉脉与迢迢。”好不容易到了牛郎和织女要相聚的时候,谁知喜鹊这儿也是一关。三只小喜鹊在这一年里存下了很多的喜鹊毛,好在七夕这天搭成鹊桥让牛郎织女团聚。每根喜鹊毛有3种属性,而每只喜鹊在意的只有其中一种属性,且他们在意的属性都不同。然而达成鹊桥只需要3根毛(为什么这么少?去问喜鹊吧,我也不知道=__=|||),每只喜鹊都会拿出自己在意的属性最大的毛,连起来成为一座鹊桥。然而,属性值越大就意味着他们要走越长时间才能相聚!所以牛郎请你去搞点小动作,把3堆毛重新分堆,好让这座鹊桥尽可能短。你能帮帮他们吗?
(鹊桥的长度即为每只喜鹊在意的属性的最大值的和。)
数据规模
对于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。
提示
一只喜鹊可以一年都没有攒到毛。
你不能把部分毛偷走。
有三只小喜鹊,她们是小爱、天天和Ylen~她们一个喜欢最漂亮的毛,一个喜欢最长的毛,一个喜欢颜色最多的毛。猜猜谁喜欢哪种毛?
样例解释:第1、2根毛的A属性最大值为1,第3根毛的B属性最大值为4,没有毛的C属性最大值为0。它们的和为5。
比赛答疑帖:http://www.rqnoj.cn/Discuss_Show.asp?DID=6785
输入包含N + 1行。
第1行,一个整数N,表示有N根喜鹊毛。
第2行到第N + 1行,三个整数Ai, Bi, Ci,表示第i根喜鹊毛属性A、B、C的值。
输出包含1行。
第1行,一个整数S,表示鹊桥长度的最小值。