Катя решила поменять пароль от своей страницы в социальной сети «Вразрыве». Она нашла в Интернете большую строку $$$s$$$, состоящую из строчных букв латинского алфавита, и решила, что ее новым паролем будет подстрока строки $$$s$$$.
Подстрока строки $$$s$$$ — это последовательность подряд идущих букв строки $$$s$$$ произвольной (возможно нулевой) длины.
Кате нужно ввести на сайт новый пароль, чтобы он обновился, но ее клавиатура очень старая. Про каждую клавишу с буквой латинского алфавита известно количество раз, которые ее еще можно нажать. После этого клавиша сломается. Например, если букву «b» можно нажать еще три раза, а букву «e» можно нажать еще два раза, то Катя сможет набрать строки «bebeb», «ee», «bbeb», но не сможет набрать строки «bbbb», «eebbe».
Катя считает, что надежность пароля определяется его длиной — чем длиннее пароль, тем он надежнее. По заданной строке $$$s$$$ найдите длину наибольшей ее подстроки, которая может стать паролем Кати, и которую она сможет набрать на своей клавиатуре.
В первой строке следует непустая строка $$$s$$$, длина которой не превышает $$$100\,000$$$. Строка $$$s$$$ состоит из строчных букв латинского алфавита.
Во второй строке следуют $$$26$$$ целых чисел $$$cnt_1, cnt_2, \dots, cnt_{26}$$$ $$$(0 \le cnt_i \le 100\,000)$$$, где $$$cnt_i$$$ — количество раз, которое можно набрать на клавиатуре $$$i$$$-ю букву латинского алфавита. То есть, $$$cnt_1$$$ — количество раз, которое можно набрать букву «a», $$$cnt_2$$$ — количество раз, которое можно набрать букву «b», и так далее.
Выведите длину наибольшей подстроки строки $$$s$$$, которая может стать паролем Кати, и которую она сможет набрать на своей клавиатуре. Обратите внимание, что эта подстрока может быть пустой. В этом случае ее длина равна $$$0$$$.
abacaba
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3
aaazazbzaaa
5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3
6
aaaaaaaaa
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0
В первом примере, например, паролем может стать подстрока «bac» длины $$$3$$$, так как каждую из букв «a», «b» и «c» можно нажать не более одного раза.
Во втором примере паролем будет строка «aaazaz» длины $$$6$$$, так как букву «b» нельзя нажимать ни одного раза.
В третьем примере пароль будет пустым, так как букву «a» нельзя нажимать ни одного раза.
