Вам надано зважений неорієнтований повний граф із \(N\) вершинами, пронумерованими від 1 до \(N\). Ребро, що з’єднує вершини \(i\) та \(j\) \((i<j)\), має вагу \(D_{i,j}\) ​.

Вибираючи деяку кількість ребер за наступної умови, знайти максимально можливу загальну вагу вибраних ребер.

• Кінцеві точки вибраних ребер попарно різні.

Обмеження

• \(2≤N≤16\)
• \(1≤D_{i,j} ​ ≤10^9\)
• Усі вхідні значення є цілими числами.

Формат вхідних даних

Вхідні дані надаються зі стандартного вводу в такому форматі:

Формат вихідних даних

У вихідний потік виведіть відповідь.

Приклад вхідних даних

4
1 5 4
7 8
6

Приклад вихідних даних

13

Якщо вибрати ребро, що з’єднує вершини 1 і 3, і ребро, що з’єднує вершини 2 і 4, загальна вага ребер буде 5 + 8=13. Можна показати, що це максимально досяжне значення.

Приклад вхідних даних

3
1 2
3

Приклад вихідних даних

3

Приклад вхідних даних

16
5 6 5 2 1 7 9 7 2 5 5 2 4 7 6
8 7 7 9 8 1 9 6 10 8 8 6 10 3
10 5 8 1 10 7 8 4 8 6 5 1 10
7 4 1 4 5 4 5 10 1 5 1 2
2 9 9 7 6 2 2 8 3 5 2
9 10 3 1 1 2 10 7 7 5
10 6 1 8 9 3 2 4 2
10 10 8 9 2 10 7 9
5 8 8 7 5 8 2
4 2 2 6 8 3
2 7 3 10 3
5 7 10 3
8 5 7
9 1
4

Приклад вихідних даних

75