Cho $n$ dãy số nguyên $A_1,A_2,…,A_n$, mỗi dãy số có $n$ phần tử.

Hãy chọn $n$ số $b_1,b_2,…,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≤n≤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,…,b_n$ thì ghi $-1$.

Ví dụ:

Input

3
1 2 3
4 5 6
7 8 9 

Output

18