Діамант#1917

Діамант

1 секунда

64 мегабайти

Легка

Ви — великий шанувальник ювелірних виробів і дорогоцінного каміння. Нещодавно у ювелірній крамниці поряд з вашим домом виставили на продаж надзвичайний діамант. Проте й ціна його була не менш вражаючою — $X$ доларів. На жаль, вам довелось визнати, що це занадто дорого для вас, незалежно від того, наскільки сильно вам подобався сам діамант.

Очевидно, що інші потенційні покупці думали так само, адже незабаром магазин почав рекламну кампанію. "Отримайте знижку $5%$ за кожну літеру у вашому імені!" — свідчив напис біля входу. Формулювання було не зовсім зрозумілим, тому ви вирішили уточнити подробиці у персоналу. Після розмови стало відомо, що:

Якщо літера зустрічається у вашому імені кілька разів, вона враховується лише один раз. Наприклад, для імені $a l e x an d r a$ alexandra для акції враховується $7$ літер, а не $9$ , оскільки $a$ зустрічається тричі.
Знижка $5%$ множиться на кількість різних літер у вашому імені. Наприклад, для $a l e x an d r a$ alexandra ви отримаєте знижку $35%$ .
Знижка понад $100%$ не надається, але можлива повна знижка у $100%$ (коли ви про це спитали, персонал подивився на вас дивно).

Звісно, було б прикро не скористатися такою щедрою пропозицією, але, можливо, ви зможете заощадити ще більше. На щастя, нещодавно ви познайомилися з людиною, яка підробляє паспорти. Його послуги оплачуються таким чином:

Підробка паспорта коштує $A$ доларів. У фальшивому паспорті може бути залишене ваше справжнє ім'я без змін, або ж ви можете змінити його, виконавши будь-яку кількість операцій трьох видів.
Вставка літери у будь-яке місце коштує $B$ доларів.
Видалення літери у будь-якому місці коштує $C$ доларів. Результуюче ім'я не повинно бути порожнім.
Заміна будь-якої літери на будь-яку іншу малу англійську літеру коштує $D$ доларів.

Дано $X$ , $A$ , $B$ , $C$ , $D$ та ваше справжнє ім'я $N am e$ , визначте мінімальну загальну суму грошей, необхідну для отримання діаманта (включаючи витрати на діамант і підробку паспорта, якщо така буде). Підробляти паспорт не обов'язково; ви можете також просто пред'явити свій справжній паспорт із ім'ям $N am e$ під час купівлі.

Вхідні дані

У першому рядку задано ціле число $X$ . У другому рядку задано цілі числа $A$ , $B$ , $C$ , $D$ ( $1 \leq X, A, B, C, D \leq 1000000$ 1 \le X, A, B, C, D \le 1000000), розділені пробілами. У третьому рядку знаходиться $N am e$ . $N am e$ містить від $1$ до $15$ символів, усі — малі латинські літери.

Вихідні дані

Виведіть мінімальну суму грошей, необхідну для отримання діаманта, у центах (у одному доларі $100$ центів).

Приклади

Приклад 1