Кубок CBOSS

В 2239 году команде-победителю Открытого кубка CBOSS достался весьма нетрадиционный приз - поездка по k самым красивым городам России. Так как в России красивых городов достаточно много, то победителям было предложено выбрать k городов из списка, содержащего n городов.

Для удобства занумеруем эти города целыми числами от 1 до n. Для каждого города известно ti - время, требующееся на осмотр его достопримечательностей. Также для каждой пары (i, j), 1 ≤ i, j ≤ n известно a_i,j - время, которое требуется на проезд из i-ого города в j-ый. При этом может оказаться, что a_i,j ≠ a_j,i, но a_i,i всегда равно нулю.

У студентов, входящих в команду-победитель, не так много времени на посещение красивых городов, ведь скоро у них сессия. Поэтому они хотят выбрать k городов и посетить их в таком порядке, чтобы затраты времени были минимальны. Разумеется, посещать один город несколько раз им неинтересно. Также они не хотят приезжать в город, не осматривая при этом его достопримечательности.

Напишите программу, находящую нужные k городов и порядок, в котором их нужно посетить.

Входные данные

Первая строка входного файла INPUT.TXT содержит целые числа n и k (1 ≤ n ≤ 7, 1 ≤ k ≤ n). Каждая из последующих n строк входного файла содержит по n целых чисел каждая: j-ое число (i + 1)-ой строки входного файла - это время, требуемое на проезд из i-ого города в j-ый (a_i,j). Последняя строка входного файла содержит n целых чисел t₁, …, t_n.

Все числа во входном файле не превосходят 100. Все времена неотрицательны.

Выходные данные

В первой строке выходного файла OUTPUT.TXT выведите минимальное время, которое потребуется для посещения k городов с учетом осмотра достопримечательностей. Во второй строке выходного файла выведите номера городов в порядке посещения, гарантирующем такое время.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]