QBGAME - Trò chơi trên ma trận

Giới hạn
  • Thời gian: 0.2s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Ngày nay các nhà khoa học đã nghĩ ra 1 trò chơi trên ma trận rất thú vị. Thông qua đó có thể đo IQ một cách khá hiệu quả. Trò chơi được mô tả như sau:

Bạn có 1 ma trận A kích thước 8 x N trên đó gồm các số nguyên là điểm của các ô đó. Người ta sẽ yêu cầu bạn chọn 1 tập khác rỗng các ô trên ma trận này sau đó tính tổng điểm trên những ô này. Trong những ô được chọn không có hai ô nào kề cạnh. IQ của người chơi sẽ tỉ lệ thuận với số điểm nhận được. Sherry tham gia trò chơi và đạt kết quả khá tốt.Và bây giờ Sherry muốn biết tổng điểm lớn nhất nhận được trong trò chơi này là bao nhiêu. Bạn hãy giúp sherry nhé !!!

Input

Dòng 1 là số nguyên N ( 1 <= N <= 10000 )

8 dòng tiếp theo: Mỗi dòng gồm n số nguyên. Số nguyên ở hàng i, cột j là A ij ( |A ij | <= 10 8 )

Output

Gồm 1 dòng duy nhất là số điểm lớn nhất tìm được

Example 

Input:
2
-22 2
-33 45
56 -60
-8 -38
79 66
-10 -23
99 46
1 -55

Output:
279

Giải thích:
 Chọn các ô (3,1) (5,1) (7,1) (2,2)

  • Người up: cun
  • Nguồn bài: Võ Khánh Trung