Торгівцю необхідно відвідати \(N\) міст, кожне по одному разу. Знайдіть найкоротший шлях.

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

В першому рядку число \(N\) - кількість міст (\(1 \le N \le 20\))
Кожен з наступних \(N\) рядків містить по \(N\) цілих чисел - відстані між відповідними містами.
В i-му рядку j-те число \(Aij\) - це відстань між містами \(i\) та \(j\) (\(0 \le Aij \le 10^6, Aij=Aji, Aii=0\))

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

Виведіть єдине число - довжину найкоротшого шляху.

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

5
0 183 163 173 181
183 0 165 172 171
163 165 0 189 302
173 172 189 0 167
181 171 302 167 0

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

666