Palindromic Subsequence in DNA

Given a DNA sequence consisting of the characters A, C, G, and T, your task is to determine whether there exists a palindromic subsequence of length (k). A subsequence is derived from the sequence by removing zero or more characters without changing the order of the remaining characters. A palindrome reads the same backwards as forwards. If such a subsequence exists, output "YES"; otherwise, output "NO".

The problem requires you to compute the length of the longest palindromic subsequence using dynamic programming and then check if it meets or exceeds (k).

inputFormat

Input is provided via standard input (stdin). The first line contains the DNA sequence (a string composed of letters 'A', 'C', 'G', 'T'). The second line contains an integer (k), representing the required length of the palindromic subsequence.

outputFormat

Output via standard output (stdout) a single line containing "YES" if there exists a palindromic subsequence of length (k); otherwise, output "NO".## sample

AGCTTAGC
4

YES