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

245. Black-White Army
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



Welcome to invincible black-white kings division, recruit! Here we will make true warriors out of you. You - best of the best, you - our new generation, we made you in our's own image, upgraded some functions. But not everyone of you can be a king... Army needs black-white knights, black-white bishops, black-white rooks and even black-white pawns. Who asks a question about black-white queens? You can completelly forget about it. It is an army, not a humanitarian faculty, son. Radiance in our blood! Forward, to training grounds!
Training grounds is an N x M chessboard, every cell of which can be empty, contain some colorless chess pieces (distance-controlled dummies), or ancient black-white king sculptures (they occupy cell as usual chess piece but can not move or attack you). You started at specified cell of the board, but before starting you must choose your chess piece. It can be any chess piece except a queen. You can make your moves according to chess rules. If after the turn you are under attack of some colorless chess piece, you lose (the training is over) and your score points is decreased by some penalty value. If you want you can leave training grounds in the beginning of any turn (not very patriotic) and do not lose any score points.
Colorless chess pieces do not make turns. After capturing colorless chess piece of some type your score is increased by a capturing bonus for that chess piece type. The number of your turns is not limited. Initially your score is 0.
You task is to achieve maximal possible score (you can lose, it is not important, all that is important - your score points after training).

Input
The first line of input contains two integers N and M (1<=N, M<=300). The second line contains seven integers: capturing bonus points for pawn, rook, knight, bishop, queen, and king respectively, and the penalty value for losing. All these numbers are non-negative and not exceed 10000.
Next N lines contain M characters each. Legend is the following: "." - empty cell, "#" - ancient black-white king sculpture, "P" - pawn, "R" - rook, "K" - knight, "B" - bishop, "Q" - queen, "M" - king, "@" - your starting point (guaranteed that it exists and exactly one). It is considered (it is important for pawns only) that colorless chess pieces are oriented in direction of decreasing line numbers, and you are oriented in the opposite direction. Notice that the third line of input is the first line of the chessboard.
For simplicity if you choose a pawn you can not change your chess piece type when moving to the last line and can not make move from the second line to the fourth.

Output
Output the maximal score you can achieve.

Sample test(s)

Input
Test #1
4 5
1 1 1 1 1 1 10
..@..
.K.K.
.Q...
.....

Test #2
4 5
1 1 1 1 5 1 3
..@..
.K.K.
.Q...
.....

Output
Test #1
1

Test #2
2
Author:	Alexey Preobrajensky
Resource:	Petrozavodsk Summer Training Sessions 2004
Date:	August 25, 2004

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

You are given an `N x M` chessboard, `N, M <= 300`.

Cells may contain:

- `.` empty cell
- `#` immovable sculpture/wall
- colorless stationary pieces:
  - `P` pawn
  - `R` rook
  - `K` knight
  - `B` bishop
  - `Q` queen
  - `M` king
- `@` your starting cell

Before training, you choose your own chess piece type: pawn, rook, knight, bishop, or king. Queen is forbidden.

You move by normal chess rules. After each move, if your current cell is attacked by any remaining stationary piece, you lose and pay a fixed penalty. You may also quit before any move without penalty.

Capturing a stationary piece removes it and gives a type-dependent bonus.

Goal: maximize final score.

---

## 2. Key observations needed to solve the problem

### Observation 1: We do not need to choose pawn

Your pawn only moves downward by one cell and captures diagonally downward. A king can simulate every possible pawn move or capture, and also has more options. Since being attacked depends only on the landing square, choosing pawn is never better than choosing king.

So we only test:

```text
rook, knight, bishop, king
```

Queen is forbidden.

---

### Observation 2: Represent safety by attack counts

For every cell, compute:

```text
attack_count[cell] = number of stationary pieces attacking this cell
```

A cell is safe iff:

```text
attack_count[cell] == 0
```

Pieces never move, but captured pieces disappear, so attack counts may decrease.

---

### Observation 3: Safe captures never create new attacks

Suppose we safely capture a piece on cell `x`.

Since `x` is safe, no rook/bishop/queen currently attacks `x`. Therefore, the captured piece is not hiding behind it any sliding attack that would be opened after removal.

So removing a safely captured piece:

- deletes that piece’s own attacks,
- never opens new sliding attacks.

Therefore during safe play, attack counts only decrease.

This is the central trick.

---

### Observation 4: For reversible pieces, safe reachable area forms a closure

Rook, bishop, knight, and king moves are reversible. If we can reach a safe cell, we can move around inside the same safe reachable region.

For one selected piece type:

1. Start from a safe seed cell.
2. Flood all safe empty cells reachable by legal moves.
3. If a reachable cell can capture a safe piece, capture it.
4. Remove its attacks.
5. Newly safe cells may become reachable.
6. Repeat until nothing changes.

All safe captures should be taken because all bonuses are non-negative and safe captures cannot hurt.

---

### Observation 5: At the end, maybe make one risky capture

After all possible free safe captures, we may optionally make one final move onto an attacked piece.

That ends the training and gives:

```text
bonus(piece) - penalty
```

If this is positive, take it. Otherwise quit safely.

Moving to an attacked empty cell is never useful because it only gives `-penalty`.

---

### Observation 6: Starting cell needs special handling

If `@` is safe, it is just the initial seed cell.

If `@` is attacked, we are allowed to stand there before the first move only. After leaving it, we cannot treat it as a normal safe cell.

So when the start is attacked, we enumerate possible first moves:

- first move to safe empty cell,
- first move capturing a safe piece,
- first move capturing an attacked piece, which is immediately a losing final move.

---

## 3. Full solution approach

### Step 1: Compute initial attack counts

For non-sliding pieces:

- pawn attacks diagonally upward because colorless pawns face decreasing row index,
- knight attacks by knight jumps,
- king attacks adjacent cells.

For sliding pieces:

- rook attacks along rows/columns,
- bishop attacks diagonals,
- queen attacks both.

Sliding attacks can be computed in `O(NM)` per direction using sweeps.

For example, when sweeping left-to-right, we keep whether the nearest blocker to the left is a rook or queen. If yes, the current cell is attacked from that direction.

There are eight sliding directions total.

---

### Step 2: Closure computation

For a chosen piece type and a set of safe starting cells:

Maintain:

```text
reachable[cell] = this safe cell is reachable
scheduled[cell] = this safe piece is scheduled for capture
risky[cell] = this attacked piece can be captured as final move
```

Use two stacks/queues:

```text
work = reachable cells whose moves should be scanned
capq = safe pieces ready to capture
```

When scanning moves from a reachable cell:

- `#` blocks movement.
- A safe piece is scheduled for capture.
- An attacked piece is remembered as a possible final risky capture.
- A safe empty cell becomes reachable.
- An attacked empty cell cannot be landed on, but sliding pieces may pass over it.

When capturing a safe piece:

1. Add its bonus.
2. Remove it from the board.
3. Mark its square reachable.
4. Decrease attack counts on cells attacked by that piece.
5. If some cell’s count becomes zero, it may now join the reachable area.

At the end, add the best positive risky capture value.

---

### Step 3: Evaluate each piece type

For each of:

```text
R, K, B, M
```

where `K` means knight and `M` means king:

- If start is safe, run closure from `@`.
- Otherwise enumerate first moves carefully.

The answer is the maximum over those four choices, at least `0` because we may quit immediately.

---

### Complexity

Let:

```text
V = N * M
```

Initial attack computation is `O(V)`.

The closure scans legal moves repeatedly. For sliding pieces, a scan may traverse a row/column/diagonal, so worst-case complexity is roughly:

```text
O(V * (N + M))
```

This is acceptable for `N, M <= 300` in C++.

---

## 4. C++ implementation with detailed comments

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

using int64 = long long;

const int64 NEG = LLONG_MIN / 4;

int n, m;
int sr, sc;

int bonusP, bonusR, bonusK, bonusB, bonusQ, bonusM;
int penalty;

vector<string> board;
vector<int> baseCnt;

const int knightD[8][2] = {
    {-2, -1}, {-2, 1}, {-1, -2}, {-1, 2},
    {1, -2},  {1, 2},  {2, -1},  {2, 1}
};

const int kingD[8][2] = {
    {-1, -1}, {-1, 0}, {-1, 1},
    {0, -1},           {0, 1},
    {1, -1},  {1, 0},  {1, 1}
};

const int rookD[4][2] = {
    {-1, 0}, {1, 0}, {0, -1}, {0, 1}
};

const int bishopD[4][2] = {
    {-1, -1}, {-1, 1}, {1, -1}, {1, 1}
};

bool inside(int r, int c) {
    return r >= 0 && r < n && c >= 0 && c < m;
}

bool isPiece(char ch) {
    return ch == 'P' || ch == 'R' || ch == 'K' ||
           ch == 'B' || ch == 'Q' || ch == 'M';
}

bool blocksRay(char ch) {
    return ch != '.' && ch != '@';
}

int getBonus(char ch) {
    if (ch == 'P') return bonusP;
    if (ch == 'R') return bonusR;
    if (ch == 'K') return bonusK;
    if (ch == 'B') return bonusB;
    if (ch == 'Q') return bonusQ;
    if (ch == 'M') return bonusM;
    return 0;
}

/*
    Iterate over legal moves of our chosen piece.

    type:
        R = rook
        B = bishop
        K = knight
        M = king

    fn(nr, nc) is called for each possible landing cell.
    For sliding pieces, if fn returns true, the ray stops.
*/
template <class F>
void forMoves(char type, int r, int c, F fn) {
    bool sliding = (type == 'R' || type == 'B');

    const int (*dirs)[2];

    if (type == 'K') dirs = knightD;
    else if (type == 'M') dirs = kingD;
    else if (type == 'R') dirs = rookD;
    else dirs = bishopD;

    int cnt = sliding ? 4 : 8;

    for (int i = 0; i < cnt; i++) {
        int nr = r + dirs[i][0];
        int nc = c + dirs[i][1];

        if (!sliding) {
            if (inside(nr, nc)) {
                fn(nr, nc);
            }
        } else {
            while (inside(nr, nc)) {
                bool stop = fn(nr, nc);
                if (stop) break;

                nr += dirs[i][0];
                nc += dirs[i][1];
            }
        }
    }
}

/*
    Iterate over all cells attacked by stationary piece t at (r, c)
    on current board g.
*/
template <class F>
void forFootprint(const vector<string>& g, char t, int r, int c, F fn) {
    auto ray = [&](int dr, int dc) {
        int nr = r + dr;
        int nc = c + dc;

        while (inside(nr, nc)) {
            fn(nr * m + nc);

            if (blocksRay(g[nr][nc])) break;

            nr += dr;
            nc += dc;
        }
    };

    auto spot = [&](int dr, int dc) {
        int nr = r + dr;
        int nc = c + dc;

        if (inside(nr, nc)) {
            fn(nr * m + nc);
        }
    };

    if (t == 'R' || t == 'Q') {
        for (auto &d : rookD) {
            ray(d[0], d[1]);
        }
    }

    if (t == 'B' || t == 'Q') {
        for (auto &d : bishopD) {
            ray(d[0], d[1]);
        }
    }

    if (t == 'K') {
        for (auto &d : knightD) {
            spot(d[0], d[1]);
        }
    } else if (t == 'M') {
        for (auto &d : kingD) {
            spot(d[0], d[1]);
        }
    } else if (t == 'P') {
        // Colorless pawns attack toward decreasing row index.
        spot(-1, -1);
        spot(-1, 1);
    }
}

/*
    Compute initial attack count for every cell.
*/
void computeBaseCnt() {
    baseCnt.assign(n * m, 0);

    auto sweep = [&](int dr, int dc, bool diagonal) {
        vector<char> active(n * m, 0);

        int r0 = dr >= 0 ? 0 : n - 1;
        int r1 = dr >= 0 ? n : -1;
        int rs = dr >= 0 ? 1 : -1;

        int c0 = dc >= 0 ? 0 : m - 1;
        int c1 = dc >= 0 ? m : -1;
        int cs = dc >= 0 ? 1 : -1;

        for (int r = r0; r != r1; r += rs) {
            for (int c = c0; c != c1; c += cs) {
                int pr = r - dr;
                int pc = c - dc;

                int attacked = 0;

                if (!inside(pr, pc)) {
                    attacked = 0;
                } else if (blocksRay(board[pr][pc])) {
                    char p = board[pr][pc];

                    if (diagonal) {
                        attacked = (p == 'B' || p == 'Q');
                    } else {
                        attacked = (p == 'R' || p == 'Q');
                    }
                } else {
                    attacked = active[pr * m + pc];
                }

                active[r * m + c] = attacked;

                if (attacked) {
                    baseCnt[r * m + c]++;
                }
            }
        }
    };

    // Rook-like sliding attacks.
    sweep(0, 1, false);
    sweep(0, -1, false);
    sweep(1, 0, false);
    sweep(-1, 0, false);

    // Bishop-like sliding attacks.
    sweep(1, 1, true);
    sweep(1, -1, true);
    sweep(-1, 1, true);
    sweep(-1, -1, true);

    // Non-sliding pieces.
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            char ch = board[r][c];

            if (isPiece(ch) && ch != 'R' && ch != 'B' && ch != 'Q') {
                forFootprint(board, ch, r, c, [&](int idx) {
                    baseCnt[idx]++;
                });
            }
        }
    }
}

/*
    Remove a piece and subtract its attacks.
*/
void uncountPiece(vector<string>& g, vector<int>& cnt, int r, int c) {
    char t = g[r][c];

    forFootprint(g, t, r, c, [&](int idx) {
        cnt[idx]--;
    });

    g[r][c] = '.';
}

/*
    Compute closure from safe seed cells.

    Returns:
        first  = score from all free safe captures
        second = best optional risky final capture value
*/
pair<int64, int64> closure(
    char type,
    vector<string> g,
    vector<int> cnt,
    const vector<pair<int, int>>& seeds
) {
    int64 freeScore = 0;

    vector<char> reachable(n * m, 0);
    vector<char> scheduled(n * m, 0);
    vector<char> riskyMark(n * m, 0);

    vector<int> work;
    vector<int> capq;
    vector<int> riskyCells;

    /*
        Check whether cell x can be connected to already reachable cells
        by one legal move of our chosen piece.
    */
    auto canPull = [&](int x) {
        bool ok = false;

        forMoves(type, x / m, x % m, [&](int nr, int nc) {
            int idx = nr * m + nc;

            if (reachable[idx]) {
                ok = true;
                return true;
            }

            return g[nr][nc] == '#' || isPiece(g[nr][nc]);
        });

        return ok;
    };

    /*
        Called when a cell's attack count becomes zero.
    */
    auto onZero = [&](int x) {
        int r = x / m;
        int c = x % m;

        if (g[r][c] == '#' || reachable[x]) return;

        if (isPiece(g[r][c])) {
            if (!scheduled[x] && canPull(x)) {
                scheduled[x] = 1;
                capq.push_back(x);
            }
        } else {
            if (canPull(x)) {
                reachable[x] = 1;
                work.push_back(x);
            }
        }
    };

    /*
        Safely capture piece at (r, c).
    */
    auto takePiece = [&](int r, int c) {
        char t = g[r][c];
        int idx = r * m + c;

        freeScore += getBonus(t);

        reachable[idx] = 1;
        g[r][c] = '.';
        work.push_back(idx);

        forFootprint(g, t, r, c, [&](int x) {
            cnt[x]--;

            if (cnt[x] == 0) {
                onZero(x);
            }
        });
    };

    /*
        Scan legal moves from reachable cell u.
    */
    auto scan = [&](int u) {
        int r = u / m;
        int c = u % m;

        forMoves(type, r, c, [&](int nr, int nc) {
            int idx = nr * m + nc;
            char ch = g[nr][nc];

            if (ch == '#') {
                return true;
            }

            if (isPiece(ch)) {
                if (cnt[idx] == 0) {
                    if (!scheduled[idx]) {
                        scheduled[idx] = 1;
                        capq.push_back(idx);
                    }
                } else {
                    if (!riskyMark[idx]) {
                        riskyMark[idx] = 1;
                        riskyCells.push_back(idx);
                    }
                }

                return true;
            }

            if (cnt[idx] == 0) {
                if (!reachable[idx]) {
                    reachable[idx] = 1;
                    work.push_back(idx);
                }

                // For sliding pieces, stop here.
                // Further cells will be found when this one is scanned.
                return true;
            }

            // Attacked empty square cannot be landed on,
            // but sliders may pass through it.
            return false;
        });
    };

    for (auto [r, c] : seeds) {
        int idx = r * m + c;

        if (!reachable[idx]) {
            reachable[idx] = 1;
            work.push_back(idx);
        }
    }

    while (!work.empty() || !capq.empty()) {
        while (!work.empty()) {
            int u = work.back();
            work.pop_back();
            scan(u);
        }

        while (!capq.empty()) {
            int p = capq.back();
            capq.pop_back();

            takePiece(p / m, p % m);
        }
    }

    int64 bestRisky = NEG;

    for (int idx : riskyCells) {
        char ch = g[idx / m][idx % m];

        if (isPiece(ch)) {
            bestRisky = max(bestRisky, (int64)getBonus(ch) - penalty);
        }
    }

    return {freeScore, bestRisky};
}

int64 closureValue(
    char type,
    const vector<string>& g,
    const vector<int>& cnt,
    const vector<pair<int, int>>& seeds
) {
    auto [freeScore, risky] = closure(type, g, cnt, seeds);

    if (risky == NEG) return freeScore;

    return freeScore + max<int64>(0, risky);
}

/*
    Flood a safe empty component.
    Used only when start is attacked, to avoid evaluating the same
    first-move component many times.
*/
void floodComponent(char type, int r, int c, vector<char>& seen) {
    vector<pair<int, int>> st;
    st.push_back({r, c});
    seen[r * m + c] = 1;

    while (!st.empty()) {
        auto [cr, cc] = st.back();
        st.pop_back();

        forMoves(type, cr, cc, [&](int nr, int nc) {
            int idx = nr * m + nc;
            char ch = board[nr][nc];

            if (ch == '#' || isPiece(ch)) {
                return true;
            }

            if (baseCnt[idx] == 0) {
                if (!seen[idx]) {
                    seen[idx] = 1;
                    st.push_back({nr, nc});
                }

                return true;
            }

            return false;
        });
    }
}

/*
    Evaluate one chosen piece type.
*/
int64 evaluateType(char type) {
    int startIdx = sr * m + sc;

    // If start is safe, closure from start is enough.
    if (baseCnt[startIdx] == 0) {
        return closureValue(type, board, baseCnt, {{sr, sc}});
    }

    // Start is attacked. First move must be handled separately.
    int64 best = 0;

    vector<pair<int, int>> safeEmptyFirstMoves;
    vector<pair<int, int>> safeCaptureFirstMoves;

    forMoves(type, sr, sc, [&](int nr, int nc) {
        int idx = nr * m + nc;
        char ch = board[nr][nc];

        if (ch == '#') {
            return true;
        }

        if (isPiece(ch)) {
            if (baseCnt[idx] == 0) {
                safeCaptureFirstMoves.push_back({nr, nc});
            } else {
                // Immediate losing final capture.
                best = max(best, (int64)getBonus(ch) - penalty);
            }

            return true;
        }

        if (baseCnt[idx] == 0) {
            safeEmptyFirstMoves.push_back({nr, nc});
        }

        return false;
    });

    // Empty first moves: evaluate one representative per safe component.
    vector<char> seen(n * m, 0);

    for (auto [r, c] : safeEmptyFirstMoves) {
        int idx = r * m + c;

        if (!seen[idx]) {
            floodComponent(type, r, c, seen);
            best = max(best, closureValue(type, board, baseCnt, {{r, c}}));
        }
    }

    // First move captures a safe piece.
    for (auto [r, c] : safeCaptureFirstMoves) {
        vector<string> g2 = board;
        vector<int> cnt2 = baseCnt;

        int firstBonus = getBonus(board[r][c]);

        uncountPiece(g2, cnt2, r, c);

        auto [freeScore, risky] = closure(type, g2, cnt2, {{r, c}});

        int64 value = firstBonus + freeScore;

        if (risky != NEG) {
            value += max<int64>(0, risky);
        }

        best = max(best, value);
    }

    return best;
}

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

    cin >> n >> m;

    cin >> bonusP >> bonusR >> bonusK >> bonusB >> bonusQ >> bonusM >> penalty;

    board.resize(n);

    for (int i = 0; i < n; i++) {
        cin >> board[i];
    }

    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            if (board[r][c] == '@') {
                sr = r;
                sc = c;
            }
        }
    }

    computeBaseCnt();

    int64 answer = 0;

    // Pawn is dominated by king. Queen is forbidden.
    for (char type : {'R', 'K', 'B', 'M'}) {
        answer = max(answer, evaluateType(type));
    }

    cout << answer << '\n';

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys

NEG = -(10 ** 30)

KNIGHT_D = [
    (-2, -1), (-2, 1), (-1, -2), (-1, 2),
    (1, -2),  (1, 2),  (2, -1),  (2, 1)
]

KING_D = [
    (-1, -1), (-1, 0), (-1, 1),
    (0, -1),           (0, 1),
    (1, -1),  (1, 0),  (1, 1)
]

ROOK_D = [(-1, 0), (1, 0), (0, -1), (0, 1)]
BISHOP_D = [(-1, -1), (-1, 1), (1, -1), (1, 1)]


def solve():
    data = sys.stdin.read().split()
    it = iter(data)

    n = int(next(it))
    m = int(next(it))

    bonus_p = int(next(it))
    bonus_r = int(next(it))
    bonus_k = int(next(it))
    bonus_b = int(next(it))
    bonus_q = int(next(it))
    bonus_m = int(next(it))
    penalty = int(next(it))

    board = [list(next(it)) for _ in range(n)]

    start_r = start_c = -1

    for r in range(n):
        for c in range(m):
            if board[r][c] == '@':
                start_r, start_c = r, c

    def inside(r, c):
        return 0 <= r < n and 0 <= c < m

    def is_piece(ch):
        return ch in "PRKBQM"

    def blocks_ray(ch):
        return ch != '.' and ch != '@'

    def get_bonus(ch):
        if ch == 'P':
            return bonus_p
        if ch == 'R':
            return bonus_r
        if ch == 'K':
            return bonus_k
        if ch == 'B':
            return bonus_b
        if ch == 'Q':
            return bonus_q
        if ch == 'M':
            return bonus_m
        return 0

    def for_moves(piece_type, r, c, fn):
        """
        Iterate over legal moves of our chosen piece.

        For sliding pieces, fn may return True to stop the ray.
        """
        if piece_type == 'K':
            dirs = KNIGHT_D
            sliding = False
        elif piece_type == 'M':
            dirs = KING_D
            sliding = False
        elif piece_type == 'R':
            dirs = ROOK_D
            sliding = True
        else:
            dirs = BISHOP_D
            sliding = True

        if not sliding:
            for dr, dc in dirs:
                nr = r + dr
                nc = c + dc

                if inside(nr, nc):
                    fn(nr, nc)
        else:
            for dr, dc in dirs:
                nr = r + dr
                nc = c + dc

                while inside(nr, nc):
                    stop = fn(nr, nc)

                    if stop:
                        break

                    nr += dr
                    nc += dc

    def for_footprint(g, piece, r, c, fn):
        """
        Iterate over cells attacked by stationary piece at (r, c).
        """

        def ray(dr, dc):
            nr = r + dr
            nc = c + dc

            while inside(nr, nc):
                fn(nr * m + nc)

                if blocks_ray(g[nr][nc]):
                    break

                nr += dr
                nc += dc

        def spot(dr, dc):
            nr = r + dr
            nc = c + dc

            if inside(nr, nc):
                fn(nr * m + nc)

        if piece == 'R' or piece == 'Q':
            for dr, dc in ROOK_D:
                ray(dr, dc)

        if piece == 'B' or piece == 'Q':
            for dr, dc in BISHOP_D:
                ray(dr, dc)

        if piece == 'K':
            for dr, dc in KNIGHT_D:
                spot(dr, dc)

        elif piece == 'M':
            for dr, dc in KING_D:
                spot(dr, dc)

        elif piece == 'P':
            # Colorless pawns attack toward decreasing row index.
            spot(-1, -1)
            spot(-1, 1)

    def compute_base_count():
        """
        Compute initial number of attacks on every cell.
        """
        cnt = [0] * (n * m)

        def sweep(dr, dc, diagonal):
            active = [0] * (n * m)

            r_range = range(n) if dr >= 0 else range(n - 1, -1, -1)
            c_range = range(m) if dc >= 0 else range(m - 1, -1, -1)

            for r in r_range:
                for c in c_range:
                    pr = r - dr
                    pc = c - dc

                    if not inside(pr, pc):
                        attacked = 0
                    elif blocks_ray(board[pr][pc]):
                        p = board[pr][pc]

                        if diagonal:
                            attacked = 1 if p == 'B' or p == 'Q' else 0
                        else:
                            attacked = 1 if p == 'R' or p == 'Q' else 0
                    else:
                        attacked = active[pr * m + pc]

                    active[r * m + c] = attacked

                    if attacked:
                        cnt[r * m + c] += 1

        # Rook-like attacks.
        sweep(0, 1, False)
        sweep(0, -1, False)
        sweep(1, 0, False)
        sweep(-1, 0, False)

        # Bishop-like attacks.
        sweep(1, 1, True)
        sweep(1, -1, True)
        sweep(-1, 1, True)
        sweep(-1, -1, True)

        # Non-sliding attacks.
        for r in range(n):
            for c in range(m):
                ch = board[r][c]

                if is_piece(ch) and ch not in "RBQ":
                    def inc(idx):
                        cnt[idx] += 1

                    for_footprint(board, ch, r, c, inc)

        return cnt

    base_count = compute_base_count()

    def uncount_piece(g, cnt, r, c):
        """
        Remove a piece from board g and subtract its attacks.
        """
        piece = g[r][c]

        def dec(idx):
            cnt[idx] -= 1

        for_footprint(g, piece, r, c, dec)

        g[r][c] = '.'

    def closure(piece_type, given_board, given_cnt, seeds):
        """
        Compute all free safe captures reachable from seed cells.

        Returns:
            free_score
            best_risky_capture_value
        """
        g = [row[:] for row in given_board]
        cnt = given_cnt[:]

        free_score = 0

        reachable = [0] * (n * m)
        scheduled = [0] * (n * m)
        risky_mark = [0] * (n * m)

        work = []
        capq = []
        risky_cells = []

        def can_pull(x):
            """
            Check whether x can be connected to already reachable cells
            by one legal move.
            """
            xr = x // m
            xc = x % m

            found = False

            def cb(nr, nc):
                nonlocal found

                idx = nr * m + nc

                if reachable[idx]:
                    found = True
                    return True

                return g[nr][nc] == '#' or is_piece(g[nr][nc])

            for_moves(piece_type, xr, xc, cb)

            return found

        def on_zero(x):
            """
            Called when attack count of x becomes zero.
            """
            r = x // m
            c = x % m

            if g[r][c] == '#' or reachable[x]:
                return

            if is_piece(g[r][c]):
                if not scheduled[x] and can_pull(x):
                    scheduled[x] = 1
                    capq.append(x)
            else:
                if can_pull(x):
                    reachable[x] = 1
                    work.append(x)

        def take_piece(r, c):
            """
            Safely capture piece at (r, c).
            """
            nonlocal free_score

            piece = g[r][c]
            idx = r * m + c

            free_score += get_bonus(piece)

            reachable[idx] = 1
            g[r][c] = '.'
            work.append(idx)

            def dec(x):
                cnt[x] -= 1

                if cnt[x] == 0:
                    on_zero(x)

            for_footprint(g, piece, r, c, dec)

        def scan(u):
            """
            Scan moves from reachable cell u.
            """
            r = u // m
            c = u % m

            def cb(nr, nc):
                idx = nr * m + nc
                ch = g[nr][nc]

                if ch == '#':
                    return True

                if is_piece(ch):
                    if cnt[idx] == 0:
                        if not scheduled[idx]:
                            scheduled[idx] = 1
                            capq.append(idx)
                    else:
                        if not risky_mark[idx]:
                            risky_mark[idx] = 1
                            risky_cells.append(idx)

                    return True

                if cnt[idx] == 0:
                    if not reachable[idx]:
                        reachable[idx] = 1
                        work.append(idx)

                    return True

                # Attacked empty cells cannot be landed on,
                # but sliding pieces may pass through them.
                return False

            for_moves(piece_type, r, c, cb)

        for r, c in seeds:
            idx = r * m + c

            if not reachable[idx]:
                reachable[idx] = 1
                work.append(idx)

        while work or capq:
            while work:
                u = work.pop()
                scan(u)

            while capq:
                p = capq.pop()
                take_piece(p // m, p % m)

        best_risky = NEG

        for idx in risky_cells:
            r = idx // m
            c = idx % m
            ch = g[r][c]

            if is_piece(ch):
                best_risky = max(best_risky, get_bonus(ch) - penalty)

        return free_score, best_risky

    def closure_value(piece_type, g, cnt, seeds):
        free_score, risky = closure(piece_type, g, cnt, seeds)

        if risky == NEG:
            return free_score

        return free_score + max(0, risky)

    def flood_component(piece_type, r, c, seen):
        """
        Flood one currently safe empty component.
        """
        stack = [(r, c)]
        seen[r * m + c] = 1

        while stack:
            cr, cc = stack.pop()

            def cb(nr, nc):
                idx = nr * m + nc
                ch = board[nr][nc]

                if ch == '#' or is_piece(ch):
                    return True

                if base_count[idx] == 0:
                    if not seen[idx]:
                        seen[idx] = 1
                        stack.append((nr, nc))

                    return True

                return False

            for_moves(piece_type, cr, cc, cb)

    def evaluate_type(piece_type):
        """
        Evaluate best possible score for one chosen piece type.
        """
        start_idx = start_r * m + start_c

        if base_count[start_idx] == 0:
            return closure_value(piece_type, board, base_count, [(start_r, start_c)])

        best = 0

        safe_empty_first_moves = []
        safe_capture_first_moves = []

        def first_cb(nr, nc):
            nonlocal best

            idx = nr * m + nc
            ch = board[nr][nc]

            if ch == '#':
                return True

            if is_piece(ch):
                if base_count[idx] == 0:
                    safe_capture_first_moves.append((nr, nc))
                else:
                    best = max(best, get_bonus(ch) - penalty)

                return True

            if base_count[idx] == 0:
                safe_empty_first_moves.append((nr, nc))

            return False

        for_moves(piece_type, start_r, start_c, first_cb)

        # Safe empty first moves: one closure per component.
        seen = [0] * (n * m)

        for r, c in safe_empty_first_moves:
            idx = r * m + c

            if not seen[idx]:
                flood_component(piece_type, r, c, seen)
                best = max(best, closure_value(piece_type, board, base_count, [(r, c)]))

        # First move captures a safe piece.
        for r, c in safe_capture_first_moves:
            g2 = [row[:] for row in board]
            cnt2 = base_count[:]

            first_bonus = get_bonus(board[r][c])

            uncount_piece(g2, cnt2, r, c)

            free_score, risky = closure(piece_type, g2, cnt2, [(r, c)])

            value = first_bonus + free_score

            if risky != NEG:
                value += max(0, risky)

            best = max(best, value)

        return best

    answer = 0

    # Queen is forbidden, pawn is dominated by king.
    for piece_type in ['R', 'K', 'B', 'M']:
        answer = max(answer, evaluate_type(piece_type))

    print(answer)


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