#2762 DNA 비밀번호

18  1 s   128 MB  

Description

평소에 문자열을 가지고 노는 것을 좋아하는 민호는 어느 날 DNA 문자열에 대하여 알게 되었다. DNA 문자열은 ‘A’, ‘C’, ‘G’, ‘T’로만 구성되어있는 문자열을 말한다. 예를 들어서 “ACKA”는 DNA 문자열이 아니지만, “ACCA”는 DNA 문자열이다.
 
이런 신비한 문자열에 완전히 매료된 민호는 길이가 S 인 임의의 DNA 문자열을 만들고, 만들어진 문자열에서 연속된 P 글자를 추출해 비밀번호로 사용하기로 마음먹었다.
 
하지만 민호는 이렇게 만든 비밀번호에는 큰 문제가 있다는 것을 발견했다. 임의의 DNA 문자열에서 연속 부분 문자열을 추출할 경우, “AAAA”와 같이 보안에 취약한 비밀번호가 만들어 질 수 있기 때문이다.
 
그래서 민호는 각 알파벳 별로 암호에 최소한으로 포함되어야 할 개수를 정하기로 했다. 원본 DNA 문자열이 “AAACCTGCCAA”이고, 민호가 만들어 낼 비밀번호는 4 글자라고 하자. 민호가 ‘A’는 1 개 이상, ‘C’는 1 개 이상, ‘G’는 1 개 이상, ‘T’는 0 개 이상 사용되어야 한다는 규칙을 정했다고 가정하다. 이 때 “ACCT”는 비밀번호가 될 수 없지만, “GCCA”는 비밀번호가 될 수 있다.
 
민호가 만든 임의의 DNA 문자열과 비밀번호이 될 수 있는 조건이 주어졌을 때, 민호가 비밀번호를 만들 수 있는 경우의 수를 계산해보자. 단, 서로 같은 문자열이더라도 추출한 위치가 다르면 다른 암호로 계산한다. 

Input

첫 줄에는 민호가 만든 DNA 문자열의 길이 S 와 비밀번호로 사용할 부분 문자열의 길이 P 가 주어진다. S 와 P 는 1 과 1,000,000 사이의 정수이며 P는 S 이하이다.
 
두 번째 줄에는 민호가 만든 DNA 문자열이 주어진다. 모든 알파벳은 대문자이다.
 
세 번째 줄에는 비밀번호에 포함되어야 할 각 알파벳의 최소 개수가 주어진다. 각각 ‘A’, ‘C’, ‘G’, ‘T’의 최소 개수를 의미한다. 각 수는 0 과 1,000,000 사이의 정수이다.

Output

첫 줄에 민호가 조건에 맞는 비밀번호를 만들어 낼 수 있는 경우의 수를 출력한다

Sample Input

Sample Output

41 30
AGGAACAGCGACTAACCCACTGAGGGTTACCTCTGCTGCTT
0 5 2 1
12

Source

shake 2016! 본선