MAXCUB - Khối lập phương lớn nhất

Giới hạn
  • Thời gian: 0.145s
  • 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

Cho một khối lập phương kích thước n chia làm n3 khối lập phương đơn vị. Mỗi khối lập phương đơn vị chứa 1 số nguyên.
Bạn hãy tìm một khối lập phương con của khối lập phương đã cho sao cho tổng các số trong khối lập phương con đó là lớn nhất.

Input

  • Dòng đầu: số lượng test.
  • Tiếp theo là các test, mỗi test gồm: dòng đầu là n. Sau đó n nhóm dòng thể hiện lớp cắt của hình lập phương nhìn từ mặt trước từ gần ra xa, mỗi nhóm gồm n dòng, mỗi dòng gồm n số liệt kê các số trên lớp cắt từ trên xuống dưới, trái qua phải.

Chú ý: n <= 30. Giá trị của khối lập phương đơn vị thuộc kiểu integer.

Output

Mỗi dòng chứa tổng của khối lập phương con lớn nhất của test tương ứng.

Example

Input
2
3
0 -1 3
-5 7 4
-8 9 1
-1 -3 -1
2 -1 5
0 -1 3
3 1 -1
1 3 2
1 -2 1
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

Output
27
64

  • Người up: dtmp