Ваш учитель дал вам последовательность мячей A, в которой каждый мяч обозначен строчной буквой латиницы 'a'-'z'. Вам не нравится заданная последовательность, вы фанат последовательности B. Чтобы превратить последовательность A в последовательность B вы можете выполнять следующие операции.
- Вы можете вставлять в последовательность любой мяч, обозначенный любой буквой, в любое место последовательности.
- Вы можете удалять (изымать) любой мяч из любого места последовательности.
- Вы можете заменить любой мяч последовательности любым другим мячом.
- Вы можете поменять местами два соседних мяча в последовательности.
Теперь ваш учитель ввел ограничения по времени на каждую операцию, то есть операцию можно выполнить только за определенное время. Таким образом, на первую операцию требуется ti единиц времени, на вторую — td, на третью — tr, а на четвертую — te. Также дано, что 2·te ≥ ti + td.
Найдите наименьшее время, необходимое для того, чтобы переделать последовательность A в последовательность B.
Выходные данные
Выведите единственное целое число — наименьшее время, необходимое для того, чтобы переделать A в B.
Примечание
Во втором примере можно было удалить мяч, обозначенный 'a', из первой позиции, а затем можно было вставить ещё одну 'a' в конец последовательности, затратив шесть единиц времени. Однако, если поменять мячи местами, то тогда будет затрачено три единицы времени.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1 1 1
youshouldnot
thoushaltnot
|
5
|
|
2
|
2 4 10 3
ab
ba
|
3
|
|
3
|
1 10 20 30
a
za
|
1
|