题目描述

“今日云骈渡鹊桥,应非脉脉与迢迢。”好不容易到了牛郎和织女要相聚的时候,谁知喜鹊这儿也是一关。三只小喜鹊在这一年里存下了很多的喜鹊毛,好在七夕这天搭成鹊桥让牛郎织女团聚。每根喜鹊毛有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,表示鹊桥长度的最小值。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论