K-Palindrome Determination

Given a string (s) and an integer (k), determine whether (s) can be transformed into a palindrome by removing at most (k) characters. A palindrome is a string that reads the same forwards and backwards. To solve this problem, you should first compute the length of the longest palindromic subsequence (LPS) in (s) and then check if (n - LPS(s) \leq k), where (n) is the length of (s).

inputFormat

The input consists of two lines:

The first line contains the string (s), composed of lowercase English letters. The second line contains an integer (k), which is the maximum number of characters that can be removed.

outputFormat

Output a single line containing either "True" or "False" (without quotes) indicating whether it is possible to convert (s) into a palindrome by removing at most (k) characters.## sample

abca
1

True