<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

535. Dirty Dishes
Time limit per test: 1 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

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.

Input
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.

Output
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.

Example(s)
sample input
sample output
ab*bB
3

sample input
sample output
afFaAA
3

sample input
sample output
**bbB*Da*
4

sample input
sample output
a**b
-1



Note
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.

<|response|>
## 1. Abridged problem statement

Jill uses one stack of dirty dishes.

- Lowercase letter `c`: Jill puts a dish of color `c` onto the stack.
- Uppercase letter `C`: Jill removes a dish of color `c` from the top of the stack.
- `*`: Jack was absent and may have missed any sequence of actions, possibly empty.

The stack is empty before and after the whole process. Given Jack’s notes, find the minimum possible number of dishes cleaned in total, or print `-1` if the notes are impossible.

The string length is at most `2500`, and there are at most `5` asterisks.

---

## 2. Key observations needed to solve the problem

### Observation 1: This is a colored bracket sequence

A lowercase letter is like an opening bracket, and the matching uppercase letter is like a closing bracket.

For example:

```text
a f F A
```

is valid, because `f` is closed by `F`, then `a` is closed by `A`.

The stack condition means that the completed action sequence must be a correctly nested colored bracket sequence.

Every dish contributes exactly two actions:

1. It is put onto the stack.
2. It is later removed.

So if the final completed sequence has length `L`, the number of dishes is `L / 2`.

---

### Observation 2: Some observed pairs are forced

Suppose we scan the notes and see a lowercase letter immediately available on top of the unresolved sequence, followed later by its matching uppercase letter.

Example:

```text
f F
```

These two actions must match each other, so we can remove them from further consideration.

If instead the unresolved top is `f` and we see `A`, this is impossible, because Jill would be trying to remove an `a`-colored dish while an `f`-colored dish is on top.

So we can greedily reduce the observed string.

---

### Observation 3: Asterisks are the only places where missing actions may be inserted

After greedy reduction, the remaining letters are actions that could not be matched using only observed actions.

We need to decide the minimum number of extra actions that the `*` positions must generate to make the whole sequence balanced.

Since there are at most `5` stars, we can afford dynamic programming on intervals.

---

### Observation 4: Useful split points are limited

After greedy reduction, between two asterisks, every ordinary block has the form:

```text
UPPERCASE...UPPERCASE lowercase...lowercase
```

There cannot be a lowercase letter followed by a matching possible uppercase letter without either cancelling or causing contradiction.

Therefore, when splitting a balanced interval into two balanced parts, it is enough to split:

1. At an asterisk.
2. Between an uppercase run and a lowercase run, i.e. at position `i` where:

```cpp
isupper(t[i]) && islower(t[i + 1])
```

Because there are at most `5` stars, the number of such split points is small.

---

## 3. Full solution approach based on the observations

Let `s` be the original input string.

### Step 1: Greedy reduction

We build a reduced string `t`.

We also count `kept`, the number of observed non-star letters. Even if two observed letters are reduced away, they still happened, so they still count toward the final number of actions.

Process every character `c` in `s`:

- If `c` is lowercase or `*`, append it to `t`.
- If `c` is uppercase:
  - If `t` ends with the matching lowercase letter, remove that lowercase letter.
  - If `t` ends with a different lowercase letter, the notes are impossible.
  - Otherwise, append the uppercase letter.

Example:

```text
afFaAA
```

Reduction:

```text
a f F  -> f and F cancel
a a A  -> second a and A cancel
a A    -> a and A cancel
```

So the reduced string becomes empty.

---

### Step 2: Interval DP

Let:

```text
dp[l][r] = minimum number of missing actions needed
           to make t[l..r] a valid balanced sequence
```

If impossible, `dp[l][r] = INF`.

Empty interval costs `0`.

---

### Endpoint transitions

#### Case 1: both endpoints are stars

A star may generate nothing useful for this interval:

```text
dp[l][r] = min(dp[l + 1][r], dp[l][r - 1])
```

---

#### Case 2: left endpoint is a star

The left star may be ignored:

```text
dp[l][r] = dp[l + 1][r]
```

If `t[r]` is uppercase, the left star can generate the matching lowercase push:

```text
dp[l][r] = dp[l][r - 1] + 1
```

---

#### Case 3: right endpoint is a star

The right star may be ignored:

```text
dp[l][r] = dp[l][r - 1]
```

If `t[l]` is lowercase, the right star can generate the matching uppercase pop:

```text
dp[l][r] = dp[l + 1][r] + 1
```

---

#### Case 4: both endpoints are observed letters

If `t[l]` is lowercase, `t[r]` is uppercase, and they have the same color, they can match:

```text
dp[l][r] = dp[l + 1][r - 1]
```

---

### Split transitions

A balanced sequence can be a concatenation of two balanced sequences.

For a normal split after position `i`:

```text
dp[l][r] = min(dp[l][r], dp[l][i] + dp[i + 1][r])
```

For a split at a star, the same star position may contribute generated actions to both sides, so the star is included in both intervals:

```text
dp[l][r] = min(dp[l][r], dp[l][i] + dp[i][r])
```

We only try the useful split points described earlier.

---

### Final answer

Let:

```text
extra = dp[0][n - 1]
```

where `n = len(t)`.

If `extra` is impossible, print `-1`.

Otherwise, total number of actions is:

```text
kept + extra
```

Each dish contributes exactly two actions, so the answer is:

```text
(kept + extra) / 2
```

---

### Complexity

There are `O(n^2)` intervals.

For each interval, we try only a small number of split points. Since there are at most `5` stars, the number of useful split points is also small.

Therefore:

```text
Time complexity:  O(n^2)
Memory complexity: O(n^2)
```

with `n <= 2500`.

---

## 4. C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

string s;
string t;
int n;

vector<vector<int>> dp;
vector<int> split_pts;

bool is_low(char c) {
    return c >= 'a' && c <= 'z';
}

bool is_up(char c) {
    return c >= 'A' && c <= 'Z';
}

char to_low(char c) {
    if (is_up(c)) return char(c - 'A' + 'a');
    return c;
}

/*
    f(l, r) returns the minimum number of extra actions that must be generated
    by stars inside t[l..r] so that this interval becomes a valid balanced
    colored bracket sequence.

    If impossible, it returns INF.
*/
int f(int l, int r) {
    // Empty interval is already balanced.
    if (l > r) {
        return 0;
    }

    int &res = dp[l][r];

    // Already computed.
    if (res != -1) {
        return res;
    }

    res = INF;

    /*
        Endpoint transitions.
    */

    // Case 1: both endpoints are stars.
    if (t[l] == '*' && t[r] == '*') {
        // Ignore left star.
        res = min(res, f(l + 1, r));

        // Ignore right star.
        res = min(res, f(l, r - 1));
    }

    // Case 2: left endpoint is a star.
    else if (t[l] == '*') {
        // Left star can generate the matching lowercase push
        // for the uppercase letter at r.
        if (is_up(t[r])) {
            res = min(res, f(l, r - 1) + 1);
        }

        // Or the left star may be ignored.
        res = min(res, f(l + 1, r));
    }

    // Case 3: right endpoint is a star.
    else if (t[r] == '*') {
        // Right star can generate the matching uppercase pop
        // for the lowercase letter at l.
        if (is_low(t[l])) {
            res = min(res, f(l + 1, r) + 1);
        }

        // Or the right star may be ignored.
        res = min(res, f(l, r - 1));
    }

    // Case 4: both endpoints are observed letters.
    else {
        // They may match if left is lowercase, right is uppercase,
        // and both colors are equal.
        if (is_low(t[l]) && is_up(t[r]) && t[l] == to_low(t[r])) {
            res = min(res, f(l + 1, r - 1));
        }
    }

    /*
        Split transitions.

        A balanced sequence can be a concatenation of two balanced sequences.

        We only try useful split points:
        - stars,
        - positions between uppercase and lowercase blocks.
    */
    for (int i : split_pts) {
        if (t[i] == '*') {
            /*
                Split at a star.

                The star can generate some actions for the left side
                and some actions for the right side, so it belongs to both
                intervals.

                We need l < i < r so both intervals are strictly smaller.
            */
            if (l < i && i < r) {
                res = min(res, f(l, i) + f(i, r));
            }
        } else {
            /*
                Normal split after position i:
                    [l..i] and [i + 1..r]
            */
            if (l <= i && i < r) {
                res = min(res, f(l, i) + f(i + 1, r));
            }
        }
    }

    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s;

    string reduced;
    int kept = 0;

    /*
        Step 1: Greedy reduction.

        Count every observed action.
        Then remove forced matching observed pairs.
    */
    for (char c : s) {
        if (c != '*') {
            kept++;
        }

        // Lowercase push or star: keep it for now.
        if (c == '*' || is_low(c)) {
            reduced.push_back(c);
        } else {
            // c is uppercase, an observed pop.

            if (reduced.empty() || reduced.back() == '*' || is_up(reduced.back())) {
                // No lowercase push directly available to match this pop.
                reduced.push_back(c);
            } else if (reduced.back() == to_low(c)) {
                // Matching lowercase exists: forced pair, remove it.
                reduced.pop_back();
            } else {
                // Top unresolved dish has a different color.
                cout << -1 << '\n';
                return 0;
            }
        }
    }

    t = reduced;
    n = (int)t.size();

    /*
        If everything reduced away, no missing action is needed.
    */
    if (n == 0) {
        cout << kept / 2 << '\n';
        return 0;
    }

    /*
        Collect useful split points.
    */
    for (int i = 0; i < n; i++) {
        if (t[i] == '*') {
            split_pts.push_back(i);
        } else if (i + 1 < n && is_up(t[i]) && is_low(t[i + 1])) {
            split_pts.push_back(i);
        }
    }

    dp.assign(n, vector<int>(n, -1));

    int extra = f(0, n - 1);

    if (extra >= INF) {
        cout << -1 << '\n';
    } else {
        cout << (kept + extra) / 2 << '\n';
    }

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys
from array import array

INF = 10 ** 9


def is_low(c):
    return 'a' <= c <= 'z'


def is_up(c):
    return 'A' <= c <= 'Z'


def solve():
    s = sys.stdin.readline().strip()

    reduced = []

    # Number of observed non-star actions.
    kept = 0

    # Step 1: Greedy reduction.
    for c in s:
        if c != '*':
            kept += 1

        # Lowercase push or star.
        if c == '*' or is_low(c):
            reduced.append(c)
        else:
            # c is uppercase, an observed pop.

            if not reduced or reduced[-1] == '*' or is_up(reduced[-1]):
                # No lowercase push directly available to match this pop.
                reduced.append(c)

            elif reduced[-1] == c.lower():
                # Matching lowercase exists: forced pair.
                reduced.pop()

            else:
                # Different lowercase is on top, impossible.
                print(-1)
                return

    t = ''.join(reduced)
    n = len(t)

    # If fully reduced, no extra missing actions are needed.
    if n == 0:
        print(kept // 2)
        return

    # Precompute character types.
    low = [is_low(c) for c in t]
    up = [is_up(c) for c in t]
    lower = [c.lower() for c in t]

    # Collect useful split points.
    split_pts = []

    for i in range(n):
        if t[i] == '*':
            split_pts.append(i)
        elif i + 1 < n and up[i] and low[i + 1]:
            split_pts.append(i)

    /*
    Python does not support C-style block comments.
    The DP below is bottom-up.

    dp[l][r] = minimum number of extra actions needed
               to balance t[l..r].
    */

    # Use arrays to reduce memory usage.
    dp = [array('i', [-1]) * n for _ in range(n)]

    # Fill intervals by increasing length.
    for length in range(1, n + 1):
        for l in range(0, n - length + 1):
            r = l + length - 1

            best = INF

            # Case 1: both endpoints are stars.
            if t[l] == '*' and t[r] == '*':
                # Ignore left star.
                if l + 1 > r:
                    val = 0
                else:
                    val = dp[l + 1][r]
                best = min(best, val)

                # Ignore right star.
                if l > r - 1:
                    val = 0
                else:
                    val = dp[l][r - 1]
                best = min(best, val)

            # Case 2: left endpoint is a star.
            elif t[l] == '*':
                # Left star generates matching lowercase push for t[r].
                if up[r]:
                    if l > r - 1:
                        val = 0
                    else:
                        val = dp[l][r - 1]
                    best = min(best, val + 1)

                # Ignore left star.
                if l + 1 > r:
                    val = 0
                else:
                    val = dp[l + 1][r]
                best = min(best, val)

            # Case 3: right endpoint is a star.
            elif t[r] == '*':
                # Right star generates matching uppercase pop for t[l].
                if low[l]:
                    if l + 1 > r:
                        val = 0
                    else:
                        val = dp[l + 1][r]
                    best = min(best, val + 1)

                # Ignore right star.
                if l > r - 1:
                    val = 0
                else:
                    val = dp[l][r - 1]
                best = min(best, val)

            # Case 4: both endpoints are observed letters.
            else:
                if low[l] and up[r] and lower[l] == lower[r]:
                    if l + 1 > r - 1:
                        val = 0
                    else:
                        val = dp[l + 1][r - 1]
                    best = min(best, val)

            # Split transitions.
            for i in split_pts:
                if t[i] == '*':
                    # Star split: [l..i] and [i..r]
                    if l < i < r:
                        val = dp[l][i] + dp[i][r]
                        if val < best:
                            best = val
                else:
                    # Normal split: [l..i] and [i+1..r]
                    if l <= i < r:
                        val = dp[l][i] + dp[i + 1][r]
                        if val < best:
                            best = val

            dp[l][r] = best

    extra = dp[0][n - 1]

    if extra >= INF:
        print(-1)
    else:
        print((kept + extra) // 2)


if __name__ == "__main__":
    solve()
```

Note: In the Python code above, replace the C-style `/* ... */` comment block with Python `#` comments before running. Here is the corrected version of that small comment section:

```python
    # The DP below is bottom-up.
    #
    # dp[l][r] = minimum number of extra actions needed
    #            to balance t[l..r].
```
