struct State {
    int row, col, value, deviceUsed;
};

const vector<pair<int, int>> directions = {{1, 0}, {1, -1}, {1, 1}};

int getMaxPseudoRandomNumber(vector<vector<int>>& unitType, int n, int m, int k) {
    vector<vector<vector<int>>> dp(n, vector<vector<int>>(m, vector<int>(2, -1)));
    queue<State> q;

    for (int j = 0; j < m; j++) {
        q.push({0, j, 0, 0});
        dp[0][j][0] = 0;
    }

    int maxValue = -1;

    while (!q.empty()) {
        State current = q.front();
        q.pop();

        int r = current.row, c = current.col, val = current.value, used = current.deviceUsed;

        for (auto [dr, dc] : directions) {
            int nr = r + dr, nc = c + dc;

            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;

            int newValue = val;
            if (unitType[nr][nc] == 1) newValue++;
            else if (unitType[nr][nc] == 2) newValue--;

            if (newValue < 0) continue;

            int newUsed = used;
            if (used == 0 && unitType[nr][nc] == 2) {
                vector<vector<int>> tempUnitType = unitType;
                for (int i = nr; i < min(n, nr + k); i++) {
                    for (int j = 0; j < m; j++) {
                        if (tempUnitType[i][j] == 2) {
                            tempUnitType[i][j] = 0;
                        }
                    }
                }
                newUsed = 1;
                if (dp[nr][nc][newUsed] < newValue) {
                    dp[nr][nc][newUsed] = newValue;
                    q.push({nr, nc, newValue, newUsed});
                }
                continue;
            }

            if (dp[nr][nc][newUsed] < newValue) {
                dp[nr][nc][newUsed] = newValue;
                q.push({nr, nc, newValue, newUsed});
                if (nr == n - 1) maxValue = max(maxValue, newValue);
            }
        }
    }

    return maxValue;
}