(maxsc.*)

Cho \(n\) dãy số nguyên \(A_{1},A_{2},\ldots,A_{n}\), mỗi dãy số có \(n\) phần tử.

Hãy chọn \(n\) số \(b_{1},b_{2},\ldots,b_{n}\) sao cho thỏa mãn đồng thời cả 3 điều kiện:

1. Số \(b_{i}\) được chọn từ dãy \(A_{i}\)

2. \(b_{i} > b_{i - 1}\)

3. Tổng các số được chọn là lớn nhất

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên \(n\ (1 \leq n \leq 10^{3})\).

+ \(n\) dòng tiếp theo, dòng thứ \(i\) ghi \(n\ \)số cho biết các số của dãy \(A_{i}\)

Kết quả:

+ Một số nguyên duy nhất cho biết tổng các số tìm được, nếu không tìm được dãy số \(b_{1},b_{2},\ldots,b_{n}\) thì ghi \(- 1\).

Ví dụ: