문제
21XX년, KOI국에서는 IOI에 나갈 3명의 국가대표를 뽑고자 한다.
그러기 위해 전국 프로그래밍 협회에서는 대회에 나갈 후보 학생 N명을 추렸다.
각 학생의 코딩 능력은 3가지 요소를 통해 수치화된다.
i번째 학생의 아이디어는 Xi, 구현력은 Yi, 운은 Zi로 표기했을 때, 각 요소에 대해 값이 클 수록 능력이 좋다고 판단한다.
21XX년의 IOI는 팀 대회이다. 즉, 개인의 능력이 높은 것도 좋지만 팀의 합도 고려해야 한다.
따라서 팀으로 선정된 모든 학생들에 대해, 다른 학생들보다 적어도 하나의 요소에 대해 능력이 좋도록 팀을 구성하고자 한다.
예를 들어서 (10, 1, 1), (1, 10, 1), (1, 1, 10)의 능력을 가진 학생 3명은 팀이 될 수 있지만,
(10, 10, 1), (1, 1, 10), (10, 9, 9)의 능력을 가진 학생 3명은 팀이 될 수 없다.
각 팀의 전력은 학생 3명의 아이디어의 최대값, 구현력의 최대값, 운의 최대값의 합으로 계산할 수 있다.
KOI국에서 꾸릴 수 있는 국가대표 팀의 최대 전력을 구하시오.
입력
첫 줄에 후보 학생의 수 N(3<=N<=150000)이 주어진다.
이후 N줄에 걸쳐 각 후보 학생의 능력 Xi, Yi, Zi가 공백으로 구분되어 주어진다. (1<=Xi, Yi, Zi<=10^8)
Subtask 1 (8점) : N<=300
Subtask 2 (25점) : N<=4000
Subtask 3 (10점) : 모든 i에 대해, Xi, Yi, Zi<=5 이다.
Subtask 4 (10점) : 모든 i에 대해, Xi, Yi, Zi<=20 이다.
Subtask 5 (10점) : 모든 i에 대해, Xi, Yi, Zi<=300 이다.
Subtask 6 (10점) : 모든 i에 대해, Xi, Yi, Zi<=4000 이다.
Subtask 7 (27점) : 제한 없음
출력
KOI국에서 꾸릴 수 있는 국가대표 팀의 최대 전력을 한 줄에 출력하시오.
만약 팀을 구성할 수 없다면 -1을 대신 출력하시오.
예제1
5
314
231
155
442
523
13
예제2
8
111
115
151
511
155
515
551
555
15
예제3
4
123
123
123
123
-1