Задача D. Выравнивание строк

Автор:М. Спорышев   Ограничение времени:10 сек
Входной файл:Стандартный вход   Ограничение памяти:1024 Мб
Выходной файл:Стандартный выход  

Условие

Вам даны:

Требуется найти выравнивание строк P и Q, максимизирующее функцию стоимости данного выравнивания.

Выравнивание двух строк это также пара строк (Q1, Q2) одинаковой длины L, состоящих из символов алфавита, и символа "-", означающего разрыв.

Стоимость выравнивания S вычисляется по формуле: S(Q1, Q2) = L − 1i = 0f(Q1[i], Q2[i]),

где f(Q1[i], Q2[i]) = D, если выполнено хотя бы одно из условий

f(Q1[i], Q2[i]) = E, если выполнено хотя бы одно из условий

Иначе f(Q1[i], Q2[i]) = R[Q1[i]][Q2[i]]

Формат входных данных

Первая строка содержит целые числа D, E.

Вторая строка содержит строку-алфавит A.

Далее |A| строк содержат по |A| целых чисел — элементы матрицы R.

Последние две строки содержат строки P и Q.

Формат выходных данных

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

В последующих двух строках выведите выравнивание.

Если оптимальных решений несколько, выведите любое из них.

Ограничения

|D, E| ≤ 1000

 − 10 ≤ Rij ≤ 10

Длина строк не превосходит 500. Строки состоят только из символов алфавита и не могут быть пустыми.

Примеры тестов

Стандартный вход Стандартный выход
1
-5 -1
AGCT
1 -1 -1 -1 
-1 1 -1 -1
-1 -1 1 -1
-1 -1 -1 1
GAAAAAAT
GAAT
-4
GAAAAAAT
G----AAT
2
0 -1
AGCT
1 -1 -1 -1 
-1 1 -1 -1
-1 -1 1 -1
-1 -1 -1 1
GAAAAAAT
GAAT
3
GAAAAAAT
G-A-A--T
3
-4 -5
AGCT
10 -1 -3 -4
-1 7 -5 -3
-3 -5 9 0
-4 -3 0 8
AGACTAGTTAC
CGAGACGT
20
--AGACTAGTTAC
CGAGAC--G-T--
4
-18 -5
AGCT
10 -1 -3 -4
-1 7 -5 -3
-3 -5 9 0
-4 -3 0 8
AGACTAGTTAC
CGAGACGT
-10
AGACTAGTTAC
---CGAGACGT

0.104s 0.011s 15