Є \(N\) кроликів пронумерованих від 1 до \(N\).
Також для кожної пари кролів відома їх сумісність.
Необхідно розбити кролів на довільну кількість груп. Кожен кріль має належати до якоїсь групи.
Якщо два кролі \(i,j\) належать до однієї групи - це дає \(Aij\) щастя.
Визначіть максимальне можливе значення щастя.

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

У першому рядку ціле число \(N\) (\(1 \le M \le 16\)).
В наступних \(N\) рядках міститься по \(N\) чисел - таблиця сумісності кроликів.
Число в \(Aij\) позначає щастя, який зараховується, якщо кролики \(i\) та \(j\) знаходяться в одній групі. \(Aij=Aji\)

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

Виведіть максимально можливе значення щастя

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

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

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

20

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

2
0 -10
-10 0

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

0