Buy 1 Get
1
One day
Alice visited Byteland to purchase jewels for her upcoming wedding anniversary.
In Byteland,
every Jewelry shop has their own discount methods to attract the customers.
One discount method called Buy1-Get1 caught Alice's attention. That is, Alice
buys one jewel, and then she can get one additional jewel with the same color
without charge by Buy1-Get1.
Alice lists
the needed jewels as a string S, each letter denotes one jewel, the same
letters denote the same colors of jewels, and the different letters denote the
different colors of jewels.
The cost of each jewel is 1. Your task is to calculate the minimum cost for
getting all the jewels Alice listed.
Input:
The first line of
input contains a string S, which represents the jewels Alice needed.
Output:
The minimum cost.
Constraints:
1 ≤ |S|
≤ 200, where |S|
represents the length of the string S.
The string S is case sensitive, and will contain only English characters in the
range [a-z], [A-Z].
|
Sample Input1:
|
Sample Input2:
|
Sample Input2:
|
|
aaaa
|
ddcd
|
Nn
|
|
Sample Output1:
|
Sample Output2:
|
Sample Output2:
|
|
2
|
3
|
2
|
Äëÿ îòïðàâêè ðåøåíèé íåîáõîäèìî