C. Покраска деревьев
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кодер ZS и Бабуин Крис прибыли в Удайлэнд! Они прогуливались по парку, в котором растут n деревьев. Друзья решили пошалить и покрасить деревья в парке. Деревья пронумерованы целыми числами от 1 до n слева направо.

Изначально, дерево i покрашено в цвет ci. Кодер ZS и Бабуин Крис знают только m цветов, поэтому 0 ≤ ci ≤ m, где ci = 0 означает, что дерево i еще не покрашено.

Кодер ZS и бабуин Крис решили красить только не покрашенные деревья, то есть деревья с ci = 0. Они могут покрасить каждое из них в один из m цветов от 1 до m. Покраска i-ого дерева в цвет j требует pi, j литров краски.

Друзья определяют красоту покраски деревьев как наименьшее количество групп последовательных деревьев (каждая группа содержит некоторый подотрезок деревьев), на которые можно разбить все n деревьев так, что каждая из групп содержит деревья одного цвета. К примеру, если деревья слева направо раскрашены в цвета 2, 1, 1, 1, 3, 2, 2, 3, 1, 3, красота покраски равна 7, так как можно разбить деревья на 7 групп последовательных деревьев одного цвета: {2}, {1, 1, 1}, {3}, {2, 2}, {3}, {1}, {3}.

Кодер ZS и Бабуин Крис хотят покрасить все не покрашенные деревья так, что красота покраски будет в точности равняться k. Друзьям нужна ваша помощь в определении минимального количества краски (в литрах), которая им понадобится для свершения задуманного.

Заметьте, что друзья не могут красить уже покрашенные деревья.

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

Первая строка содержит три целых числа n, m и k (1 ≤ k ≤ n ≤ 100, 1 ≤ m ≤ 100) — количество деревьев, количество цветов и красоту результата покраски соответственно.

Вторая строка содержит n целых чисел c1, c2, ..., cn (0 ≤ ci ≤ m) — исходные цвета деревьев. ci равно 0, если дерево номер i не покрашено, в противном случае цвет i-го дерева равен ci.

Далее следуют n строк. Каждая из них содержит m целых чисел. j-ое число в i-ой из них равно pi, j (1 ≤ pi, j ≤ 109) — количество литров краски, необходимое для того, чтобы покрасить i-ое дерево в цвет j. pi, j определены и для изначально покрашенных деревьев, но эти деревья все равно не могут быть покрашены.

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

Выведите единственное целое число — минимальное количество краски, необходимое для покраски деревьев. Если корректной покраски деревьев красоты k не существует, выведите  - 1.

Примеры
Входные данные
3 2 2
0 0 0
1 2
3 4
5 6
Выходные данные
10
Входные данные
3 2 2
2 1 2
1 3
2 4
3 5
Выходные данные
-1
Входные данные
3 2 2
2 0 0
1 3
2 4
3 5
Выходные данные
5
Входные данные
3 2 3
2 1 2
1 3
2 4
3 5
Выходные данные
0
Примечание

В первом примере из условия покраска деревьев в цвета 2, 1, 1 минимизирует количество используемой краски, равное 2 + 3 + 5 = 10. Заметьте, что 1, 1, 1 не является корректной покраской, так как ее красота равна 1 ({1, 1, 1} является способом разбиения деревьев на одну группу деревьев одного цвета).

Во втором примере из условия все деревья покрашены, но красота покраски равна 3, поэтому правильной покраски не существует и ответ равен  - 1.

В последнем примере из условия все деревья покрашены и красота покраски равна k, поэтому краска не используется и ответ равен 0.