<|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 `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 `dp[l][r]` be the 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:
`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: `dp[l][r] = dp[l + 1][r]`.

If `t[r]` is uppercase, the left star can generate the matching lowercase push:
`dp[l][r] = dp[l][r - 1] + 1`

---

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

The right star may be ignored: `dp[l][r] = dp[l][r - 1]`.

If `t[l]` is lowercase, the right star can generate the matching uppercase pop:
`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:
`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`:
`dp[l][r] = min(dp[l][r], dp[l][i] + dp[i + 1][r])`

For a split at a `*`, the same star position may contribute generated actions to both sides, so the star is included in both intervals:
`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 `extra = dp[0][n - 1]` where `n = len(t)`.

If `extra` is impossible, print `-1`. Otherwise, total number of actions is `kept + extra`. Each dish contributes exactly two actions, so the answer is `(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;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int INF = 1e9;

string s;
string t;
int n;
vector<vector<int>> dp;
vector<int> split_pts;

void read() { cin >> s; }

int f(int l, int r) {
    if(l > r) {
        return 0;
    }

    int& res = dp[l][r];
    if(res != -1) {
        return res;
    }

    res = INF;

    if(t[l] == '*' && t[r] == '*') {
        res = min(res, f(l + 1, r));
        res = min(res, f(l, r - 1));
    } else if(t[l] == '*') {
        if(isupper(t[r])) {
            res = min(res, f(l, r - 1) + 1);
        }
        res = min(res, f(l + 1, r));
    } else if(t[r] == '*') {
        if(islower(t[l])) {
            res = min(res, f(l + 1, r) + 1);
        }
        res = min(res, f(l, r - 1));
    } else if(islower(t[l]) && isupper(t[r]) && t[l] == (char)tolower(t[r])) {
        res = min(res, f(l + 1, r - 1));
    }

    for(int i: split_pts) {
        int lo = (t[i] == '*') ? l + 1 : l;
        if(i >= lo && i < r) {
            int rl = (t[i] == '*') ? i : i + 1;
            res = min(res, f(l, i) + f(rl, r));
        }
    }

    return res;
}

void solve() {
    // First sweep greedily cancels adjacent matched pairs: lowercase 'x'
    // followed by uppercase 'X' is a real push-pop pair, so pop them off a
    // stack. A lowercase top against a non-matching uppercase is an outright
    // contradiction => -1. After this reduction, t consists of stars and
    // chains shaped like upper-upper-...upper-lower-lower-...lower (any pops
    // that survive must precede any pushes that survive, otherwise they'd
    // have cancelled). Only stars can balance what remains.
    //
    // f(l, r) = min number of extra letters the stars in t[l..r] must produce
    // so that t[l..r] becomes a fully balanced bracket sequence (lowercase =
    // open, uppercase = close). Endpoint cases handle stars at the borders
    // absorbing one neighbor as their matching bracket, and a matched pair at
    // the borders. We also try every "natural split" point: a star (which can
    // split into two stars covering both halves) or a position between an
    // uppercase and a lowercase (the only place an outer balanced sequence
    // can be cut in two without crossing an active matching pair).

    string reduced;
    int kept = 0;
    for(char c: s) {
        if(c != '*') {
            kept++;
        }

        if(c == '*' || islower(c)) {
            reduced.push_back(c);
        } else if(reduced.empty() || reduced.back() == '*' || isupper(reduced.back())) {
            reduced.push_back(c);
        } else if(reduced.back() == (char)tolower(c)) {
            reduced.pop_back();
        } else {
            cout << -1 << '\n';
            return;
        }
    }

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

    split_pts.clear();
    for(int i = 0; i < n; i++) {
        if(t[i] == '*' || (i + 1 < n && isupper(t[i]) && islower(t[i + 1]))) {
            split_pts.push_back(i);
        }
    }

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

    int extra = (n == 0) ? 0 : f(0, n - 1);
    if(extra >= INF) {
        cout << -1 << '\n';
    } else {
        cout << (extra + kept) / 2 << '\n';
    }
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys
from array import array

INF = 10 ** 9


def solve():
    # Read Jack's notes.
    s = sys.stdin.readline().strip()

    # This will store the reduced form after deleting forced observed matches.
    reduced = []

    # Number of observed non-star letters.
    # These actions always count in the final total.
    kept = 0

    # Greedy reduction.
    for ch in s:
        # Count every observed action.
        if ch != '*':
            kept += 1

        # A star or lowercase push is appended directly.
        if ch == '*' or ('a' <= ch <= 'z'):
            reduced.append(ch)

        else:
            # ch is uppercase, meaning an observed pop.

            # If there is no lowercase push immediately available to match,
            # keep this uppercase as unresolved.
            if not reduced or reduced[-1] == '*' or ('A' <= reduced[-1] <= 'Z'):
                reduced.append(ch)

            # If the previous unresolved symbol is the matching lowercase,
            # this observed pair is forced and can be removed.
            elif reduced[-1] == ch.lower():
                reduced.pop()

            # Otherwise the top dish would have the wrong color.
            else:
                print(-1)
                return

    # Reduced string.
    t = ''.join(reduced)

    # Length of reduced string.
    n = len(t)

    # If everything was reduced away, no missing action is needed.
    if n == 0:
        print(kept // 2)
        return

    # Precompute character types for speed and clarity.
    is_low = [('a' <= c <= 'z') for c in t]
    is_up = [('A' <= c <= 'Z') for c in t]

    # lowercase version of each character, used for comparing colors.
    lower = [c.lower() for c in t]

    # Collect useful split points.
    split_pts = []

    for i in range(n):
        # Split at a star.
        if t[i] == '*':
            split_pts.append(i)

        # Split between an uppercase block and lowercase block.
        elif i + 1 < n and is_up[i] and is_low[i + 1]:
            split_pts.append(i)

    # dp[l][r] = minimum number of inserted actions needed
    # to make t[l..r] balanced.
    #
    # Using array('i') keeps memory much smaller than a list of Python ints.
    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

            # Start as impossible.
            best = INF

            # Case 1: both endpoints are stars.
            if t[l] == '*' and t[r] == '*':
                # Ignore/drop left star for this segment.
                val = 0 if l + 1 > r else dp[l + 1][r]
                if val < best:
                    best = val

                # Ignore/drop right star for this segment.
                val = 0 if l > r - 1 else dp[l][r - 1]
                if val < best:
                    best = val

            # Case 2: left endpoint is a star.
            elif t[l] == '*':
                # If right endpoint is uppercase, left star can generate
                # its matching lowercase push.
                if is_up[r]:
                    val = 0 if l > r - 1 else dp[l][r - 1]
                    if val + 1 < best:
                        best = val + 1

                # Or left star contributes nothing useful here.
                val = 0 if l + 1 > r else dp[l + 1][r]
                if val < best:
                    best = val

            # Case 3: right endpoint is a star.
            elif t[r] == '*':
                # If left endpoint is lowercase, right star can generate
                # its matching uppercase pop.
                if is_low[l]:
                    val = 0 if l + 1 > r else dp[l + 1][r]
                    if val + 1 < best:
                        best = val + 1

                # Or right star contributes nothing useful here.
                val = 0 if l > r - 1 else dp[l][r - 1]
                if val < best:
                    best = val

            # Case 4: both endpoints are observed letters.
            # They may match if left is lowercase, right is uppercase,
            # and both have the same color.
            elif is_low[l] and is_up[r] and lower[l] == lower[r]:
                val = 0 if l + 1 > r - 1 else dp[l + 1][r - 1]
                if val < best:
                    best = val

            # Try all useful split points.
            for i in split_pts:
                # Star split:
                # The star can be shared by both sides,
                # so split as [l..i] and [i..r].
                if t[i] == '*':
                    if l < i < r:
                        val = dp[l][i] + dp[i][r]
                        if val < best:
                            best = val

                # Ordinary split after position i:
                # split as [l..i] and [i+1..r].
                else:
                    if l <= i < r:
                        val = dp[l][i] + dp[i + 1][r]
                        if val < best:
                            best = val

            # Store answer for interval [l, r].
            dp[l][r] = best

    # Minimum missing actions for the whole reduced string.
    extra = dp[0][n - 1]

    # If impossible, report -1.
    if extra >= INF:
        print(-1)
    else:
        # Total actions = observed actions + inserted actions.
        # Each dish has exactly one push and one pop.
        print((kept + extra) // 2)


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