Nguồn: https://uva.onlinejudge.org
(Đóng góp của Đinh Nguyên Khôi)
Alice và Bob cả hai đều có kẹo nhiều ơi là nhiều !
Nhưng mà tụi nó muốn ăn. Cho nên hai đứa nó quyết định chơi một trò chơi theo
lượt như sau:
Tụi nó sẽ điền vào một cái bảng M
có kích thước N x N với những số nguyên bất kỳ. Alice sẽ bắt đầu trò chơi bằng
cách kẻ ngang những một hàng i mà nó chưa kẻ. Bây giờ tới lượt của Bob, nó phải
kẻ dọc cột j mà trước đó nó chưa kẻ. Sau khi lượt của Bob kết thúc, Alice sẽ
lấy được số kẹo mà giao ở cột i và hàng j là M(i, j). Nếu như M(i, j) < 0,
tức là điều này đồng nghĩa với việc Alice sẽ phải đưa cho Bob M(i, j) viên kẹo.
Trò chơi sẽ kết thúc khi toàn bộ các cột và hàng đều được kẻ rồi. (Xem hình để
biết thêm chi tiết).
Nhiệm vụ của bạn rất là đơn giản
thôi ! Hãy tính xem Alice có thể lấy được nhiều nhất là bao nhiêu viên kẹo, hay
nói cách khác, là tính xem Bob lấy được ít nhất bao nhiêu viên. Giả sử hai
người này đều chơi tối ưu.
Input: Dòng đầu là số nguyên t (1 <=
t <= 20), là số test case trong một test.
Mỗi test case sẽ bắt đầu bởi một số nguyên N (1≤N≤ 8), là kích thước của cái bảng.
N dòng sau, mỗi dòng có N số nguyên. Số nguyên thứ j trên dòng thứ i là M(i , j).
Mỗi test case sẽ bắt đầu bởi một số nguyên N (1≤N≤ 8), là kích thước của cái bảng.
N dòng sau, mỗi dòng có N số nguyên. Số nguyên thứ j trên dòng thứ i là M(i , j).
Output:
Gồm t dòng, dòng thứ i tương ứng với test case thứ i, chỉ in ra một số nguyên
duy nhất là số lượng kẹo nhiều nhất mà Alice có thể ăn được.
Ví dụ:
|
INPUT
|
OUTPUT
|
|
3
2 10 10
-5 -5
2
10 10
-5 -5
2
10 -5
-5 10
|
5
5
-10
|
