Продавець акваріумів

Продавець акваріумів для котів хоче об'їехати n міст, відвідавши кожне з них рівно один раз. Допоможіть йому знайти найкоротший шлях.

Вхідні дані

Перший рядок вхідного файлу містить натуральне число n (1 ≤ n ≤ 13) - кількість міст. Наступні n рядків містять n чисел - довжини шляхів між містами.

У i-ому рядку j-те число, a_{i,j} - це відстань між містами i та j (0 ≤ a_{i,j} ≤ 10^6, a_{i,j} = a_{j,i}, a_{i,i} = 0).

Вихідні дані

У першому рядку вихідного файлу виведіть довжину найкоротшого шляху. У другому рядку виведіть n чисел - порядок, у якому потрібно відвідати міста.

Приклади