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

Условие

Вам даны:

• Числа D, E — штрафы за начало нового разрыва в выравнивании строк и штраф за его продолжение соответственно.

• Алфавит символов в виде строки A, состоящей из заглавных латинских букв.

• Матрица замен символов R, соответствующая стоимости сопоставления каждой пары символов при выравнивании строк. Строки и столбцы матрицы соответствуют символам алфавита в том порядке, в котором они указаны в строке A

• Две строки P и Q.

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

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

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

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

• Q₁[i] равен "-", а Q₁[i − 1] не равен "-"
• Q₂[i] равен "-", а Q₂[i − 1] не равен "-"

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

• Q₁[i] равен "-", и Q₁[i − 1] равен "-"
• Q₂[i] равен "-", и Q₂[i − 1] равен "-"

Иначе f(Q₁[i], Q₂[i]) = R[Q₁[i]][Q₂[i]]

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

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

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

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

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

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

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

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

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

Ограничения

|D, E| ≤ 1000

 − 10 ≤ R_ij ≤ 10

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

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

-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

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

-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--

-18 -5
AGCT
10 -1 -3 -4
-1 7 -5 -3
-3 -5 9 0
-4 -3 0 8
AGACTAGTTAC
CGAGACGT

-10
AGACTAGTTAC
---CGAGACGT