C. Последовательность мячей
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Ваш учитель дал вам последовательность мячей A, в которой каждый мяч обозначен строчной буквой латиницы 'a'-'z'. Вам не нравится заданная последовательность, вы фанат последовательности B. Чтобы превратить последовательность A в последовательность B вы можете выполнять следующие операции.

  • Вы можете вставлять в последовательность любой мяч, обозначенный любой буквой, в любое место последовательности.
  • Вы можете удалять (изымать) любой мяч из любого места последовательности.
  • Вы можете заменить любой мяч последовательности любым другим мячом.
  • Вы можете поменять местами два соседних мяча в последовательности.

Теперь ваш учитель ввел ограничения по времени на каждую операцию, то есть операцию можно выполнить только за определенное время. Таким образом, на первую операцию требуется ti единиц времени, на вторую — td, на третью — tr, а на четвертую — te. Также дано, что 2·te ≥ ti + td.

Найдите наименьшее время, необходимое для того, чтобы переделать последовательность A в последовательность B.

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

В первой строке входного файла записаны через пробел четыре целых числа ti, td, tr, te (0 < ti, td, tr, te ≤ 100). В следующих двух строках записаны последовательности A и B каждая на отдельной строке. Длина каждой строки находится на интервале от 1 до 4000 букв включительно.

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

Выведите единственное целое число — наименьшее время, необходимое для того, чтобы переделать A в B.

Примеры
Входные данные
1 1 1 1
youshouldnot
thoushaltnot
Выходные данные
5
Входные данные
2 4 10 3
ab
ba
Выходные данные
3
Входные данные
1 10 20 30
a
za
Выходные данные
1
Примечание

Во втором примере можно было удалить мяч, обозначенный 'a', из первой позиции, а затем можно было вставить ещё одну 'a' в конец последовательности, затратив шесть единиц времени. Однако, если поменять мячи местами, то тогда будет затрачено три единицы времени.