Constructing a Palindrome

You are given a string s and an integer k. You are allowed to insert at most k extra characters anywhere in s. Your goal is to determine if it is possible to rearrange the characters of s (after performing at most k insertions) so that the resulting string is a palindrome.

A palindrome is a string that reads the same forwards and backwards. To form a palindrome, the frequency of characters must satisfy the condition that at most one character has an odd frequency. In cases where more than one character has an odd frequency, you may insert additional characters to pair them up. Specifically, the minimum number of insertions required is given by the formula:

\(\left\lfloor \frac{\text{oddCount}}{2} \right\rfloor\)

If this number is less than or equal to k, it is possible to form a palindrome, and you should output YES; otherwise, output NO.

inputFormat

The input consists of two lines:

• The first line contains the string s (a non-negative string of lowercase English letters).
• The second line contains an integer k (the maximum number of characters that may be inserted).

outputFormat

Output a single line: YES if it is possible to rearrange the string into a palindrome by inserting at most k characters; otherwise, output NO.

## sample

annb
1

YES

</p>