DNA Password

Minho likes playing with strings, and he learned about DNA strings. A DNA string is a string in which every character is one of 'A', 'C', 'G', 'T'. For example, "ACKA" is not a DNA string, but "ACCA" is. Minho decided to build one DNA string and use a substring of it as a password.

Minho then noticed a serious problem with that plan. Taking an arbitrary substring can produce a weak password such as "AAAA". So Minho made a rule: a substring can be used as a password only if each character appears in it at least a fixed number of times.

Suppose the DNA string is "AAACCTGCCAA" and the length of the substring to take is 4. Suppose also that a substring can be used as a password only if it contains at least one 'A', at least one 'C', at least one 'G', and at least zero 'T'. Then "ACCT" cannot be used as a password because it fails the requirement of at least one 'G'. On the other hand "GCCA" satisfies every requirement, so it can be used as a password.

Given the DNA string Minho built, the length of the substring used as a password, and how many times each of 'A', 'C', 'G', 'T' must appear at minimum, write a program that counts the passwords Minho can make. Two substrings taken from different positions count as different strings even when they are equal as strings.

The first line contains the length $|S|$ of the DNA string Minho built and the length $|P|$ of the substring used as a password. ($1 \le |P| \le |S| \le 1{,}000{,}000$)

The second line contains the DNA string Minho built.

The third line contains the minimum counts of 'A', 'C', 'G', 'T' that the substring must contain, separated by spaces. Each number is a non-negative integer at most $|S|$, and the sum of the four numbers is guaranteed to be at most $|S|$.

Print the number of passwords Minho can make on the first line.