Palindromic Score

You are given a string \( S \) consisting of lowercase English letters. Your task is to calculate its palindromic score, which is defined as the number of characters in \( S \) that can be rearranged to form a palindrome.

A palindrome is a string that reads the same forwards and backwards. In order to form a palindrome, characters can be rearranged arbitrarily. The optimal strategy is to use as many characters as possible in pairs, and if there is any leftover character from an odd frequency, it can be used as the center of the palindrome. Formally, if a character appears \( f \) times, you can use \( f - (f \bmod 2) \) of them, plus one extra if there is at least one odd occurrence in total, resulting in the final score.

For example, for the string "abccccdd":

[ \begin{aligned} \text{Used counts} = & 1 \text{ (for 'a')} + 1 \text{ (for 'b')} + 4 \text{ (for 'c')} + 2 \text{ (for 'd')} \ &= 7. \end{aligned} ]

inputFormat

The input consists of a single line containing the string \( S \). The string may be empty or have up to \(10^5\) lowercase English letters.

outputFormat

Output a single integer representing the palindromic score of the given string \( S \).

abccccdd

7