Cho đồ thị vô hướng đầy đủ có \(N\) đỉnh (được đánh số từ \(1\) đến \(N\)). Cạnh nối đỉnh \(i\) và đỉnh \(j\) sẽ có trọng số bằng \(D_{i,j}\). Lưu ý rằng \(D_{i,j}=D_{j,i}\) với mọi cặp \(i \ne j\).

Hãy tìm cách chọn ra một tập cạnh sao cho tổng trọng số của chúng là lớn nhất và các đầu mút của chúng không trùng nhau (nói cách khác, hai cạnh \((u,v)\) và \((p,q)\) khác nhau bất kỳ trong tập được chọn ra phải thỏa mãn \(u\), \(v\), \(p\), \(q\) là bốn số nguyên phân biệt).

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) \(\left(2\le N\le 16\right)\).
• Dòng tiếp theo chứa \(N-1\) số nguyên dương \(D_{1,2}\), \(D_{1,3}\), \(D_{1,4}\),..., \(D_{1,N}\).
• Dòng tiếp theo chứa \(N-2\) số nguyên dương \(D_{2,3}\), \(D_{2,4}\), \(D_{2,5}\),..., \(D_{2,N}\).
• Dòng tiếp theo chứa \(N-3\) số nguyên dương \(D_{3,4}\), \(D_{3,5}\), \(D_{3,6}\),..., \(D_{3,N}\).
• ...
• Dòng cuối cùng chứa một số nguyên dương \(D_{N-1,N}\).
• Dữ liệu đảm bảo \(2\le D_{i,j}\le 10^9\) với mọi \(i\ne j\).

Output

• In ra tổng trọng số lớn nhất của tập cạnh tìm được.

Ví dụ

Sample input 01

4
1 5 4
7 9
6

Sample output 01

14

Giải thích

Ta có thể chọn các cạnh \((1,3)\) và \((2,4)\) để được tổng trọng số \(5+9=14\).

Sample input 02

3
1 2
4

Sample output 02

4