Có \(N\) con thỏ được đánh số \(1,2,3,...,N\)

Với mỗi \(i,j(1\le i,j\le N)\), độ "tâm đầu ý hợp" của con thỏ \(i\) và \(j\) được kí hiệu bởi một số nguyên \(a_{i,j}\). Ở đây \(a_{i,i}=0\) với mọi \(i(1\le i\le N),a_{j,i}=a_{i,j}\) với mọi \(i,j(1\le i,j\le N)\).

\(Kaninho\) chia \(N\) con thỏ này thành nhiều nhóm. Ở đây, mỗi con thỏ thuộc về chính xác \(1\) nhóm. Sau khi chia xong, với mỗi cặp \(i,j(1\le i<j\le N)\). \(Kaninho\) sẽ kiếm được \(a_{i,j}\) điểm nếu con thỏ \(i\) và \(j\) cùng thuộc về một nhóm.

Tìm số điểm tối đa mà \(Kaninho\) có thể thu được.

Input

• Dòng thứ nhất chứa số nguyên \(N\).
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên \(a_{i,1},a_{i,2},...,a_{i,N}\) thể hiện độ "tâm đầu ý hợp" của những chú thỏ với nhau.

Output

• In ra kết quả cần tìm.

Constraints

• \(1\le i\le N,|a_{i,j}|\le 10^9\)
• \(1\le N\le 16\)

Example

3
0 10 20
10 0 -100
20 -100 0 

20