Hè 2012, trường ĐHCN sẽ tổ chức kỳ thi theo mô hình ACM cho các trường phổ thông. Mỗi trường sẽ chọn ra một đội gồm 3 thí sinh để thi đấu. Để chuẩn bị tốt cho kỳ thi, trường XYZ đã có kế hoạch tập huấn cho N học sinh với 11 chủ đề sau:
Kết thúc khoá tập huấn, Ban giám hiệu đã thống kê khả năng của từng học sinh và muốn chọn ra 3 học sinh để lập thành đội đi thi với hi vọng đạt kết quả cao nhất. Giả sử Si,j là điểm đánh giá khả năng của học sinh i với chủ đề j thì việc đánh giá khả năng đạt kết quả cao của đội gồm 3 thí sinh x, y, z bằng Tổng của Max (Sx,j, Sy,j, Sz,j) với j=1→11.
Yêu cầu: Cho N học sinh và Si,j là khả năng của học sinh i với chủ đề j, hãy giúp Ban giám hiệu trường chọn ra 3 học sinh thành một đội thi đấu có khả năng đạt kết quả cao nhất.
Dữ liệu:
Hai số liên tiếp trên cùng một dòng được ghi cách nhau bởi dấu cách.
Kết quả:
Khả năng đạt kết quả cao nhất của đội có 3 thí sinh được chọn.
Input
4
2 2 2 0 0 0 0 0 0 0 0
3 1 1 0 0 0 0 0 0 0 0
1 3 1 0 0 0 0 0 0 0 0
1 1 3 0 0 0 0 0 0 0 0
Output
9
Giới hạn
Subtask 1: n<=100 [50 tests]
Subtask 2: n<=3000 [25 tests]
Subtask 3: n<=30000 [25 tests]
Nguồn: 3D 20152016