Có \(N\) chú hải ly tại Đại học JOI. Tất cả đều tham gia lập trình thi đấu. Mỗi chú hải ly có ba năng lực: khả năng tư duy, khả năng cài đặt và may mắn. Giá trị của một năng lực càng lớn thì năng lực đó càng cao. Với mỗi \(i\) (\(1\le i\le N\)), khả năng tư duy, khả năng cài đặt và may mắn của chú hải ly \(i\) lần lượt là \(X_i,Y_i,Z_i\).

Năm nay, các chú hải ly của Đại học JOI sẽ tham gia một cuộc thi lập trình theo đội. Trong cuộc thi, các thí sinh giải các bài toán lập trình và mỗi đội gồm ba chú hải ly. Bitaro là huấn luyện viên của Đại học JOI. Vì tinh thần đồng đội rất quan trọng, Bitaro quyết định chọn ba chú hải ly trong số \(N\) chú để lập một đội thỏa mãn điều kiện sau:

Điều kiện: Mỗi thành viên đều có một thế mạnh. Nghĩa là mỗi thành viên có ít nhất một năng lực với giá trị lớn hơn hẳn giá trị của cùng năng lực đó ở cả hai thành viên còn lại.

Trong số các đội thỏa mãn điều kiện, Bitaro muốn chọn đội có tổng năng lực lớn nhất. Tổng năng lực của một đội được định nghĩa là tổng của ba giá trị: khả năng tư duy lớn nhất, khả năng cài đặt lớn nhất và may mắn lớn nhất trong số các thành viên của đội.

Viết chương trình nhận thông tin về năng lực của mỗi chú hải ly, xác định có thể lập một đội thỏa mãn điều kiện hay không và, nếu có, tính tổng năng lực lớn nhất có thể của đội.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. Tất cả các giá trị đều là số nguyên.

N
X_1 Y_1 Z_1
X_2 Y_2 Z_2
...
X_N Y_N Z_N

Dữ liệu ra

Ghi một dòng ra đầu ra chuẩn, chứa tổng năng lực lớn nhất có thể của một đội. Nếu không thể lập đội thỏa mãn điều kiện, in -1.

Ràng buộc

• \(3\le N\le 150\,000\).
• \(1\le X_i\le 100\,000\,000=10^8\) với \(1\le i\le N\).
• \(1\le Y_i\le 100\,000\,000=10^8\) với \(1\le i\le N\).
• \(1\le Z_i\le 100\,000\,000=10^8\) với \(1\le i\le N\).

Phân nhóm

1. \(8\) điểm: \(N\le 300\).
2. \(29\) điểm: \(N\le 4\,000\).
3. \(9\) điểm: \(X_i,Y_i,Z_i\le 5\) với mọi \(1\le i\le N\).
4. \(9\) điểm: \(X_i,Y_i,Z_i\le 20\) với mọi \(1\le i\le N\).
5. \(9\) điểm: \(X_i,Y_i,Z_i\le 300\) với mọi \(1\le i\le N\).
6. \(9\) điểm: \(X_i,Y_i,Z_i\le 4\,000\) với mọi \(1\le i\le N\).
7. \(27\) điểm: Không có ràng buộc bổ sung.

Ví dụ

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

13

8
1 1 1
1 1 5
1 5 1
5 1 1
1 5 5
5 1 5
5 5 1
5 5 5

15

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

-1

Nguồn

JOI 2021/2022 Spring Training Camp, Contest 2, do Japanese Committee for the International Olympiad in Informatics (JCIOI) công bố. Bản dịch tiếng Việt được chuyển ngữ từ đề chính thức và phát hành theo giấy phép CC BY-SA 4.0.