시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2 2 2 100.000%

문제

알파벳 소문자로 이루어진 문자열 s가 주어진다. 알파벳 중에서 일부는 좋고, 나머지는 나쁘다.

문자열 s = s1s2...s|s|(|s|는 문자열 s의 길이)의 부분 문자열 s[l...r] (1 ≤ l ≤ r ≤ |s|)는 slsl+1...sr 이다.

만약, s[l...r]을 이루고 있는 알파벳 sl, sl+1, ..., sr 중에서 나쁜 알파벳의 개수가 최대 k개라면, 그 부분 문자열을 좋다고 한다.

s의 서로 다른 좋은 부분 문자열의 개수를 찾는 프로그램을 작성하시오. s[x...y] ≠ s[p...q]인 경우에 두 부분 문자열 s[x...y]와 s[p...q]를 서로 다르다고 한다.

입력

첫째 줄에 알파벳 소문자로 이루어진 문자열 s가 주어진다. s의 길이는 1500을 넘지 않는다.

둘째 줄에는 26개의 0과 1로 이루어진 문자열이 주어진다. i번째 글자가 1인 경우에는 i번째 알파벳이 좋은 알파벳이라는 것, 0인 경우는 나쁜 알파벳이라는 것을 의미한다. 즉, 첫 번째 문자는 알파벳 'a'를 나타내며, 두 번째 문자는 'b'를 나타낸다.

셋째 줄에는 k (0 ≤ k ≤ |s|)가 주어진다.

출력

s의 서로 다른 좋은 부분 문자열의 개수를 출력한다.

예제 입력

ababab
01000000000000000000000000
1

예제 출력

5

예제 입력 2

acbacbacaa
00000000000000000000000000
2

예제 출력 2

8

힌트

출처