400356: GYM100151 D Dirty Dishes

They say there are three things that one cannot have enough of looking at: they are the fire burning, the water flowing and others working. Jack and Jill have been married for several years but Jack never gets tired of watching Jill cleaning the kitchen in her swift and neat way!

As Jill is cleaning the kitchen, she piles up the dirty dishes by the sink. Each newly found dirty dish is put on the top of the pile and when Jill wants to wash the dishes, she takes a dish from the top of the pile.

Jack has been watching his wife attentively and each time she added a new dirty c-colored dish to the pile, Jack made a note in his notebook that a c-colored dish had been added to the pile. Similarly, when Jill took a c-colored dish from the top of the pile, Jack noted that a c-colored dish had been taken from the pile. From time to time Jack would leave to get more popcorn and then he would probably miss some of Jill's actions. In this case he wrote an asterisk "*" in his notebook.

Next day, as Jack was scanning through the notes, he got interested: what is the least number of dirty dishes that could be on the kitchen before the cleaning? Note that Jill doesn't arrange the dishes in more than one pile. Jill only puts the dishes to the top of the pile and only takes them from the top of the pile. Before the cleaning and after it the pile is empty.

The only input line contains the notes from Jack's notebook. Using Latin alphabet, he wrote a lowercase letter if Jill added a dish of the corresponding color to the pile. Also, Jack wrote an uppercase letter if Jill took a dish of the corresponding color from the pile. For example, the string "afFaAA" represents the following actions:

• Jill adds an a-colored dish to the pile,
• Jill adds an f-colored dish to the pile,
• Jill takes an f-colored dish from the pile,
• Jill adds an a-colored dish to the pile,
• Jill takes an a-colored dish from the pile,
• Jill takes an a-colored dish from the pile.

An "*" represents the periods of time when Jack went to get more popcorn and could have missed one or more Jill's actions. It is guaranteed that Jack went to get more popcorn no more than five times. So the number of characters "*" doesn't exceed 5.

The given string consists of lowercase and uppercase Latin letters and asterisks "*". It is not empty and contains no more than 2500 characters. The input contains at least one letter.

On the first line of the input file print the single number — the least possible number of dirty dishes on the kitchen before the cleaning. Print -1 if Jack's notes surely have a mistake and there's no solution.

ab*bB

3

afFaAA

3

**bbB*Da*

4

a**b

-1

An example of a sequence of actions for the first sample is abBAbB.

In the second sample Jack never left the room.

In the third sample he left the room four times, two of them one after another. An example of Jill's action succession is like that: "bbBdDaAB".

The fourth sample illustrates no solution.