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