{"raw_statement":[{"iden":"statement","content":"Guga was bored, so he decided to read the dictionary and learned a new word: \n\n_madam_, _hannah_, _x_ e _redivider_ are examples of palindromes.\n\nAnalyzing some words, Guga realized the most of them weren't palindromes and decided to create a new category called _K-Palindrome_, defined as follows: \n\nFor example, _xyz_ is not a palindrome, but is a 1-Palindrome, because we can substitute the x with a z and obtain _zyz_. On the other hand, _abcb_ is neither a palindrome nor a 1-Palindrome, but it is a 2-Palindrome, for we can substitute two letters and obtain a palindrome.\n\nWith this new definition, Guga was able to find many more words that satisfied it.\n\nWhile researching on palindromes, Guga discovered the following problem: given a string S, how many continuous substrings of S are palindromes?\n\nIntrigued, he decided to create an equivalent problem: given a string S and an integer K, how many continuous substrings of S are K-palindromes?\n\nGuga thinks it's very easy to find a wrong answer to his problem with large strings, and want a computer program that solve it. Help Guga (:\n\nEach test case consists of two lines.\n\nThe first line contains a string S (1 ≤ |S| ≤ 3000) composed only of lowercase letters, the string in which Guga wants to find the K-Palindromes.\n\nThe second line contains an integer K (0 ≤ K ≤ |S| / 2), the number of letters that can be substituted in S.\n\nThe output consists of a single line containing an integer X, the number of substrings of S that are K-palindromes.\n\nBy definition: \n\n"},{"iden":"input","content":"Each test case consists of two lines.The first line contains a string S (1 ≤ |S| ≤ 3000) composed only of lowercase letters, the string in which Guga wants to find the K-Palindromes.The second line contains an integer K (0 ≤ K ≤ |S| / 2), the number of letters that can be substituted in S."},{"iden":"output","content":"The output consists of a single line containing an integer X, the number of substrings of S that are K-palindromes."},{"iden":"examples","content":"Inputovo1Output6Inputovo0Output4"},{"iden":"note","content":"By definition:   Every _K-Palindrome_ is also a _K'-Palindrome_, where K' > K.  Every palindrome is a 0-palindrome. "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ S $ be a string of length $ n $, with $ S[i] \\in \\{a, b, \\dots, z\\} $ for $ i \\in \\{1, \\dots, n\\} $.  \nLet $ K \\in \\mathbb{Z} $, $ 0 \\leq K \\leq \\lfloor n/2 \\rfloor $.  \n\nA substring $ S[i:j] $ (with $ 1 \\leq i \\leq j \\leq n $) is a **$ K $-palindrome** if the minimum number of character substitutions required to make it a palindrome is at most $ K $.  \n\n**Constraints**  \n1. $ 1 \\leq |S| \\leq 3000 $  \n2. $ 0 \\leq K \\leq \\lfloor |S|/2 \\rfloor $  \n\n**Objective**  \nCount the number of contiguous substrings $ S[i:j] $ such that the edit distance (under substitution only) from $ S[i:j] $ to some palindrome is $ \\leq K $.  \n\nEquivalently, for each substring $ T = S[i:j] $, let $ d(T) $ be the minimum number of substitutions needed to make $ T $ a palindrome. Then:  \n$$\nX = \\left| \\left\\{ (i,j) \\mid 1 \\leq i \\leq j \\leq n,\\ d(S[i:j]) \\leq K \\right\\} \\right|\n$$  \nwhere  \n$$\nd(T) = \\sum_{k=1}^{\\lfloor |T|/2 \\rfloor} \\mathbb{1}_{T[k] \\neq T[|T|+1-k]}\n$$","simple_statement":"Given a string S and an integer K, count how many contiguous substrings of S can become palindromes by changing at most K characters.","has_page_source":false}