Какой самый дешевый тур?

Вася решил немного попутешествовать и выяснил, что между некоторыми городами нет прямых авиарейсов, поэтому придётся лететь с пересадками. Ему стало интересно, можно ли запланировать замкнутый маршрут (который начинается и заканчивается в одном и том же городе), в котором ровно K перелётов. Среди всех таких маршрутов Вася хочет выбрать самый дешёвый. Напишите программу, которая находит самый дешевый замкнутый маршрут, состоящий из K перелётов.

Входные данные
В первой строке вводится количество городов на карте N ( 1 ≤ N ≤ 8 ). В следующих N строках записано по N неотрицательных целых чисел (не превышающих 1000), разделённых пробелами – элементы весовой матрицы графа, который описывает схему авиационных сообщений. Элемент на пересечении строки i и столбца j означает стоимость перелёта между городами i и j. Ноль указывает на отсутствие прямого рейса. В последней строке вводится значение K (2 ≤ K ≤ 8).

Выходные данные
В первой строчке выводится стоимость оптимального перелёта, а во второй - последовательность городов, которые нужно посетить. Нумерация городов начинается с единицы. Последовательность посещаемых городов должна быть записана, начиная с города с наименьшим номером на этом маршруте. Если найдено несколько подходящих маршрутов одинаковой стоимости, нужно выбрать из них такой маршрут, в котором на каждом шаге выбирается следующий город с наименьшим возможным номером. Маршрут не должен проходить дважды через один и тот же город. Если ни одного подходящего маршрута нет, нужно вывести число 0.

Примеры
входные данные
5
0 2 3 5 0
2 0 4 0 1
3 4 0 6 3
5 0 6 0 0
0 0 0 4 0
3
выходные данные
9
1 2 3 1

0