Парейдолія – це явище, при якому ваші очі схильні бачити у зображеннях знайомі візерунки, яких насправді не існує - наприклад, бачення обличчя у хмарі. Оскільки фермер Джон постійно знаходиться поряд із коровами, він часто бачить коров'ячі візерунки у повсякденних предметах. Наприклад, якщо він дивиться на рядок "bqessiyexbesszieb", очі фермера Джона ігнорують деякі літери та все, що він бачить, це «bessiexbessieb» — рядок, що містить два послідовні підрядки, рівні "bessie".

Даний рядок довжиною не більше \(2\cdot 10^5\), що складається тільки із символів a-z, де кожен символ має пов'язану вартість видалення, обчисліть максимальну кількість безперервних підрядків, рівних "bessie", які ви можете сформувати, вилучивши нуль або більше символів із нього, та мінімальну загальну вартість символів, яку вам потрібно видалити, щоб зробити це.

Формат вхідних даних

Перший рядок містить рядок. Другий рядок містить вартість видалення пов'язану з кожним символом (ціле число в діапазоні \([1,1000]\)).

Формат вихідних даних

Максимальна кількість входжень та мінімальна вартість створення цього числа входжень.

Приклад вхідних даних

besssie
1 1 5 4 6 1 1

Приклад вихідних даних

1
4

Видавши букву 's' у позиції 4, ми можемо зробити весь рядок "bessie". символ у позиції 4 має вартість 4\(, тому наша відповідь: вартість 4\) за 1~. екземпляр "bessie", і це найкраще, що ми можемо зробити.

Приклад вхідних даних

bebesconsiete
6 5 2 3 6 5 7 9 8 1 4 5 1

Приклад вихідних даних

1
21

Видавши "con" у позиціях 5-7, ми можемо зробити рядок "bebessiete" у якого є bessie посередині. Позиції 5-7 коштують \(5 + 7 + 9 = 21 \), тому наша відповідь: вартість \(21\) за \(1\) екземпляр "bessie" - це найкраще, що ми можемо робити.

Приклад вхідних даних

besgiraffesiebessibessie
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Приклад вихідних даних

2
7

Цей зразок задовольняє обмеження другого підзавдання.

Видавши "giraffe" в позиціях 4-10, ми можемо зробити рядок "bessiebessibessie", на початку і в кінці якого є "bessie". "giraffe" має 7 символів, і всі символи коштують 1 долар, тому наша відповідь коштує 7 доларів за \(2\) екземплярів "bessie", це найкраще, що ми можемо зробити.

ОЦІНКА:

• Тести 4–5: \(N\le 2000\)
• Тести 6–8: усі витрати дорівнюють 1~
• Тести 9–17: додаткових обмежень немає.