Привітання

Обмеження: 2 сек., 256 МіБ

Одного вечора Зеник вирішив привітати Марічку з приходом весни й написати їй дуже гарне SMS-повідомлення. Початково Зеник увів на телефоні повідомлення \(s\), але через декілька хвилин подумав, що краще було б увести повідомлення \(t\).

На жаль, змінити повідомлення на телефоні Зеника так просто не можна. Все, що Зеник тепер може робити — це видаляти перше або останнє входження будь-якої букви. Зауважте, що Зеник може виконати цю операцію скільки завгодно раз. Більше того, символи не видаляються моментально. Видалення символу, який початково був на \(i\)-й позиції в рядку \(s\), займе \(w_i\) секунд.

Допоможіть Зенику знайти мінімальну кількість часу, за яку він може перетворити повідомлення \(s\) в \(t\) описаним вище процесом. Якщо ж перетворити повідомлення неможливо, виведіть You better start from scratch man....

Вхідні дані

У першому рядку задано рядок \(s\), а у другому — рядок \(t\).

У третьому рядку задано \(|s|\) чисел, розділених пробілами — кількість секунд, необхідна для видалення відповідного символу в \(s\).

Вихідні дані

Якщо Зеник може перетворити повідомлення \(s\) в \(t\), у єдиному рядку виведіть мінімальну кількість часу (в секундах) необхідну для цього.

Якщо ж це неможливо, виведіть You better start from scratch man....

Обмеження

\(1 \le |s|, |t| \le 2\cdot 10^5\),

\(1 \le w_i \le 10^9\),

рядки \(s\) і \(t\) складаються лише із маленьких латинських символів a-z.

Приклади