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

View as PDF

Submit solution


Points: 0.27 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type
Allowed languages
C, C++, Java, Pascal, Python, TEXT

Cho một khối lập phương kích thước ~n~ chia làm ~n^{3}~ 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 \leq 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.

Sample 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

Sample Output

27
64

Comments

Please read the guidelines before commenting.


There are no comments at the moment.