Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P176PROE - ROUND 6E - Chuỗi con đẹp

Bạn được cho một chuỗi s, bao gồm các chữ cái tiếng anh in thường. Một số chữ cái tiếng anh là đẹp, những chữ còn lại là xấu.

Một chuỗi con s[l...r] (1 ≤ l ≤ r ≤ |s|) của chuỗi s  =  s1s2...s|s| (với |s| là độ dài của chuỗi s) là chuỗi slsl + 1...sr.

Một chuỗi con s[l...r] là đẹp, nếu trong tất cả chữ cái  sl, sl + 1, ..., sr có nhiều nhất k chữ cái xấu (xem giải thích của test để hiểu rõ hơn).

Nhiệm vụ của bạn là tìm ra số lượng các chuỗi con đẹp khác nhau của chuỗi đã cho. Hai chuỗi con  s[x...y] và s[p...q] được cho là khác nhau nếu nội dung của chúng khác nhau, tức là s[x...y] ≠ s[p...q].

Input

Dòng đầu tiên chứa một chuỗi không rỗng s, gồm chữ cái tiếng anh in thường, độ dài của chuỗi tối đa là 1500 kí tự.

Dòng thứ hai chứa một chuỗi chỉ bao gồm các kí tự  "0" và "1", có độ dài chính xác là 26 kí tự.

Nếu kí tự thứ i của chuỗi bằng "1" thì chữ cái tiếng anh thứ i là đẹp, nếu không nó là xấu. Tức là, kí tự đầu tiên của chuỗi này tương ứng với chữ "a", kí tự chứ hai tương ứng với chữ "b" và vân vân.

Dòng thứ ba chứa một số nguyên k k (0 ≤ k ≤ |s|) – số lượng lớn nhất của các chữ cái xấu trong một chuỗi con đẹp.

Output

In ra số nguyên duy nhất – số lượng chuỗi con đẹp của chuỗi s.

Example

Test 1:
Input:
ababab
01000000000000000000000000
1
Output:
5
Test 2:
Input:
acbacbacaa
00000000000000000000000000
2
Output:
8

Giải thích:
- Test 1: Có các chuỗi con đẹp sau : "a", "ab", "b", "ba", "bab".
- Test 2: Có các chuỗi con đẹp sau :  "a", "aa", "ac", "b", "ba", "c", "ca", "cb".


Được gửi lên bởi:adm
Ngày:2017-03-24
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.