Задача №3789. Сохранить энергию
Одна Фруктовая Компания, производящая электронику, решила озаботиться длительностью работы своих смартфонов от аккумулятора.
Выяснилось, что процессор, который они закупают у азиатского поставщика, поддерживает m различных режимов работы, при этом каждая из k операций языка программирования (который Фруктовая Компания использует для написания всех своих программ) может быть выполнена в каждом из режимов. Одновременно процессор может работать только в одном режиме, но перед выполнением каждой из операций можно один раз переключиться в любой другой режим работы.
Известно количество единиц энергии, которое тратится для исполнения каждой из операций в каждом режиме, а также сколько энергии тратится на переключение между режимами. Требуется написать программу, определяющую, какое минимальное количество энергии необходимо потратить для выполнения заданной программы.
В начале выполнения программы процессор находится в первом режиме, завершиться выполнение программы может при любом режиме процессора.
Первая строка содержит три целых числа: число k (1 ≤ k ≤ 100) — количество операций в языке программирования, число m (1 ≤ m ≤ 100) — количество режимов работы, которое поддерживает процессор, и число n (1 ≤ n ≤ 10000) — количество операций в исследуемой программе.
Следующие k строчек содержат по m целых неотрицательных чисел, не превышающих 100. j-е число в i-ой строчке обозначает, сколько энергии тратится на выполнение i-ой операции в j-ом режиме команд.
Далее следует m строчек, содержащих по m целых неотрицательных чисел, не превышающих 100. j-ое число в i-ой строчке обозначает, сколько единиц энергии тратится на переключение процессора с режима i на режим j. Гарантируется, что в i-ой строке i-ое число равно 0.
Последняя строчка содержит исследуемую программу: n натуральных чисел, не превышающих k и соответствующих операциям языка программирования.
Выведите одно число — минимальное количество единиц энергии, необходимое для выполнения программы.
Тесты к этой задаче состоят из трех групп.
- Тесты из условия, оцениваются в ноль баллов.
- В тестах этой группы \(n\), \(m\), \(k\) не превосходят 10. Эта группа оценивается в 50 баллов, баллы ставятся только при прохождении всех тестов группы.
- В тестах этой группы \(m\) не превосходит 10. Эта группа оценивается в 30 баллов, баллы ставятся только при прохождении всех тестов группы и предыдущих групп.
- В тестах этой группы дополнительные ограничения отсутствуют. Группа оценивается в 20 баллов, баллы ставятся только при прохождении всех тестов этой и предыдущих групп.
2 1 4 60 93 0 1 2 1 1
273
2 2 4 1 10 10 1 0 1 2 0 1 1 2 2
5