Задача №112128. Аппликатура
Одна из проблем при игре на фортепьяно — выбор хорошей «аппликатуры», то есть определение для каждого звука мелодии (клавиши инструмента) пальца руки, которым эту ноту лучше всего сыграть в данном месте мелодии.
Пронумеруем пальцы пианиста слева направо натуральными числами от 1 до P, клавиши инструмента также пронумеруем слева направо натуральными числами от 1 до K. Тогда запись звуков мелодии можно представить в виде последовательности N номеров клавиш, которые следует нажимать для ее исполнения, где N — длина мелодии.
Пусть для каждой пары пальцев с номерами i и j заданы целые числа aij и bij, такие, что если палец i нажимает клавишу X, то следующей клавишей пальцем j может быть нажата лишь клавиша из диапазона [X + aij, X + bij]. Этот набор чисел aij, bij, 1 ≤ i ≤ P, 1 ≤ j ≤ P, зависит от особенностей пианиста и его исполнительской техники. Заметим, что не каждая мелодия может быть сыграна конкретным пианистом при указанных выше ограничениях.
Назовем перекладыванием пальцев ситуацию, когда для двух последовательно исполняемых нот мелодии клавиша с большим номером нажимается пальцем с меньшим номером. Требуется написать программу, которая для заданной мелодии определяет аппликатуру с наименьшим количеством перекладываний пальцев.
В первой строке входного файла содержится число P — количество пальцев у пианиста (1 ≤ P ≤ 20). Во второй строке записано число K — количество клавиш у инструмента (1 ≤ K ≤ 10000). В третьей строке указаны целые числа a11b11a12b12...a1Pb1Pa21b21a22b22...a2Pb2P...aP1bP1aP2bP2...aPPbPP, разделенные пробелами ( - K ≤ aij ≤ bij ≤ K). В четвертой строке находится число N — длина мелодии (1 ≤ N ≤ 1000). Пятая строка содержит N чисел X1X2...XN — последовательность разделенных пробелами номеров клавиш для исполнения мелодии.
В первой строке выходного файла должно содержаться либо число L — количество перекладываний пальцев в оптимальной аппликатуре, либо число - 1 при невозможности сыграть мелодию. Вторая строка при наличии решения должна содержать N чисел Y1...YN — последовательность разделенных пробелами номеров пальцев при исполнении мелодии.
3 10 0 0 -2 -2 -5 1 2 3 8 10 0 1 2 10 -2 -2 -1 -1 9 4 5 7 7 7 6 8 7 5
3 1 3 1 1 3 3 1 3 2