Longest Palindromic Subsequence

Given a string ( s ) consisting of lowercase English letters, determine the length of the longest palindromic subsequence that can be formed from it. A subsequence is a sequence derived from the string by deleting some or no characters without changing the order of the remaining characters.

The formula to calculate the maximum possible palindrome length is given by:

[ \text{max extunderscore length} = \sum_{c \in [a,z]} (f(c) - (f(c) \bmod 2)) + \begin{cases} 1 & \text{if any } f(c) \text{ is odd} \ 0 & \text{otherwise} \end{cases} ]

Here, ( f(c) ) is the frequency of character ( c ) in ( s ). Your solution should read the input from standard input and output the result to standard output.

inputFormat

The input consists of a single line containing the string ( s ).

outputFormat

Output a single integer which is the length of the longest palindromic subsequence.## sample

abca

3