[SGU535] Dirty Dishes

题目描述

Jill 在清理厨房时使用一个盘子堆。每发现一个脏盘子，她就把它放到栈顶；洗盘子时，她只会从栈顶取走一个盘子。每个盘子都有一种颜色，用一个英文字母表示。清理开始前和结束后，这个栈都是空的。

Jack 观察 Jill 的操作并做记录：

• 小写字母 c 表示 Jill 把一个颜色为 c 的盘子放到栈顶；
• 大写字母 C 表示 Jill 从栈顶取走一个对应颜色的小写字母 c 的盘子；
• * 表示 Jack 离开了一段时间。在这段时间里他可能漏记了若干次操作；这个时间段也可能恰好没有发生操作。

Jack 最多离开 $5$ 次，因此字符串中 * 的数量不超过 $5$。

请根据记录判断，整个清理过程中最少可能涉及多少个脏盘子。每个盘子恰好对应一次入栈和一次出栈。如果记录不可能由任何合法的栈操作序列产生，输出 -1。

输入格式

一行一个非空字符串 $s$，仅包含大小写英文字母和 *。

满足：

• $|s|\le 2500$；
• * 的数量不超过 $5$；
• $s$ 中至少包含一个字母。

输出格式

输出一个整数，表示最少可能涉及的脏盘子数量；若记录必然有误、无合法解释，则输出 -1。

样例

样例输入 1

ab*bB

样例输出 1

3

样例输入 2

afFaAA

样例输出 2

3

样例输入 3

**bbB*Da*

样例输出 3

4

样例输入 4

a**b

样例输出 4

-1

样例说明

第一组样例可以对应完整操作序列 abBAbB。

第二组样例中 Jack 没有离开过。

第三组样例的一种合法完整操作序列为 bbBdDaAB。