K-Palindrome

You are given a string s and an integer k. Your task is to determine whether the string s can be transformed into a palindrome by removing at most k characters.

A string is called a palindrome if it reads the same forward and backward. In this problem, you need to check if it is possible to make s a palindrome by deleting at most k characters.

The problem can be formalized using the concept of the longest palindromic subsequence (LPS). Let n be the length of the string and L be the length of its longest palindromic subsequence. Then, s can be transformed into a palindrome by at most k deletions if and only if:

\( n - L \le k \)

For example, for s = "abca" and k = 1, the answer is True because by removing the character 'b' or 'c', the resulting string is a palindrome.

inputFormat

The input is read from standard input and consists of two lines:

1. The first line contains the string s.
2. The second line contains the integer k.

outputFormat

Output to standard output a single line: True if the string can be transformed into a palindrome by removing at most k characters, otherwise False.

## sample

abca
1

True

</p>