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

423. Battle
Time limit per test: 0.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



There are n cities on a small island, numbered 1 through n. Some pairs of cities are connected with bidirectional roads. All the cities were independent. All the cities lived in harmony with each other.

One day two cities s and t decided to create their own countries and conquer some of the other independent cities. We'll denote the country started by city s as the first country, and the country started by city t as the second country.

Suppose some day the first country contains cities from A = {a1,..., aka} and the second country contains cities from B = {b1,..., bkb}. We define neigh(A) as set of cities connected with some city from A by a road, but not from A itself (so ). We also define popul(i) as the population of city i, and .

The first country can conquer a set C of independent cities at once iff  In a similar manner the second country can conquer the set C at once iff .

In the morning of each day the first country can conquer some cities, and in the evening the second country can conquer some cities.

The first country wants to conquer the cities in such a way that in the end popul(A) - popul(B) is maximal possible, and the second country wants to conquer the cities in such a way that in the end popul(B) - popul(A) is maximal possible.

Input
The first line contains three positive integers n, s and t (3 ≤ n ≤ 13, 1 ≤ s, t ≤ n, s ≠ t). Next n lines contain n characters each, with the j-th character in the i-th of those lines being '1' if cities i and j are connected by a road, and '0' otherwise. The next line contains n integers popul(i) () — the populations of all cities.

Output
Output the final value of popul(A) - popul(B) assuming that both countries act optimally.

Example(s)
sample input
sample output
5 1 2
00111
00001
10010
10101
11010
12 100 5 5 7
-85

sample input
sample output
3 1 3
010
101
010
5 5 11
-11

sample input
sample output
7 1 5
0100011
1010001
0101001
0010100
0001000
1000001
1110010
90 20 20 10 200 85 80
85

<|response|>
## 1) Abridged problem statement (concise)

There are `n ≤ 13` cities with undirected roads and population `pop[i]`. City `s` starts country **A**, city `t` starts country **B** (they are initially owned).

At any moment, A owns set `A`, B owns set `B`, remaining cities are **free**.  
For a set `X`, `neigh(X)` is the set of cities adjacent to any city in `X`, excluding `X` itself.

On A’s turn (morning), A may conquer **any non-empty subset** `C` of free cities in one move iff:

`pop(neigh(C) ∩ A) > pop(C) + pop(neigh(C) ∩ B)`.

On B’s turn (evening), B may conquer `C` iff:

`pop(neigh(C) ∩ B) > pop(C) + pop(neigh(C) ∩ A)`.

If the current player has no legal move, they pass. The game ends when neither can move (or no free cities remain).  
Both play optimally: A maximizes final `pop(A) - pop(B)`, B minimizes it.

Output the final optimal value `pop(A) - pop(B)`.

---

## 2) Key observations

1. **Small n ⇒ bitmasks are natural.**  
   With `n ≤ 13`, represent any set of cities as an integer mask `0..(1<<n)-1`.

2. **Moves are subsets, not single cities.**  
   A move can take *any subset* of currently free cities that satisfies the inequality. This forces us to consider submasks of the free set.

3. **This is a finite, deterministic, zero-sum game.**  
   Perfect information, alternating turns ⇒ solve with **minimax + memoization**.

4. **State = ownership of each city + whose turn.**  
   Each city is in one of three states: `free / A / B` ⇒ total states `3^n` (≤ 1.59M).  
   Add a “turn” bit (`A` to move or `B` to move).

5. **Fast evaluation requires precomputation.**
   - `popSum[mask]` = sum of populations in a mask.
   - `neighMask[mask]` = union of neighbors of all nodes in `mask`, minus `mask` itself.

6. **Passing logic matters.**
   - If current player has a legal move: must choose (minimax).
   - If current player has no move but opponent does: pass (switch turn).
   - If neither has a move: terminal score is `pop(A)-pop(B)`.

---

## 3) Full solution approach

### A) Precompute helper arrays (over subsets)

Let `full = (1<<n)-1`.

1. **Population sums**  
   Compute `popSum[mask]` for all masks using low-bit DP:
   ```
   popSum[0]=0
   popSum[mask] = popSum[mask without lowest bit] + pop[lowestBitIndex]
   ```

2. **Neighbor masks**  
   Store each city’s adjacency as a bitmask `adj[i]`. Then:
   ```
   neighMask[mask] = (OR over i in mask of adj[i]) & ~mask
   ```

This makes these quantities O(1):
- `pop(neigh(C) ∩ A) = popSum[neighMask[C] & A]`
- `pop(neigh(C) ∩ B) = popSum[neighMask[C] & B]`
- `pop(C) = popSum[C]`

### B) Encode states in base-3 (ternary)

We need memoization over disjoint `(A,B)` pairs. Using two masks `(A,B)` directly works too, but ternary indexing packs it into one number in `0..3^n-1`:

For each city `i`:
- digit `0` = free
- digit `1` = owned by A
- digit `2` = owned by B

This yields a unique index `idx`. Maintain **two DP tables**:
- `dpA[idx]` = optimal result when it’s A to move
- `dpB[idx]` = optimal result when it’s B to move

To update `idx` fast when taking a subset `C`, precompute:
- `pow3[i] = 3^i`
- `pow3Subset[mask] = sum(pow3[i] for i in mask)`

Then:
- If A takes `C`: `idx += pow3Subset[C]` (digits 0→1)
- If B takes `C`: `idx += 2*pow3Subset[C]` (digits 0→2)

### C) Minimax recursion with memoization

Define `solve(A_mask, B_mask, idx, who)` returning optimal final score `pop(A)-pop(B)` from this state.

Let:
- `free = full ^ A_mask ^ B_mask` (since disjoint)
- `terminal = popSum[A_mask] - popSum[B_mask]`

Enumerate all **non-empty submasks** `C ⊆ free` via:
```
for (C = free; C; C = (C-1) & free)
```

For each `C`, compute:
- `pa = popSum[neighMask[C] & A_mask]`
- `pb = popSum[neighMask[C] & B_mask]`
- `pc = popSum[C]`

Validity:
- A can take `C` iff `pa > pc + pb`
- B can take `C` iff `pb > pc + pa`

Transition:
- If `who==A` (maximize): consider all A-valid `C`, take maximum of next states.
- If `who==B` (minimize): consider all B-valid `C`, take minimum.

Passing / terminal:
- If current player has no valid move:
  - if opponent also has no valid move ⇒ return `terminal`
  - else pass ⇒ return `solve(A_mask, B_mask, idx, who^1)`

Complexity is acceptable for `n≤13` with bitmasks and memoization.

---

## 4) C++ implementation (detailed comments)

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

/*
  Battle (p423) solution:
  - n <= 13, use bitmasks for sets of cities.
  - Game state: each city is free / owned by A / owned by B => 3^n states.
  - Minimax with memoization, enumerating all submasks of currently free cities.
*/

static const long long SENT_A = LLONG_MIN; // sentinel for dpA (uncomputed)
static const long long SENT_B = LLONG_MAX; // sentinel for dpB (uncomputed)

int n, s, t;
vector<int> adj;              // adj[i] is bitmask of neighbors of i
vector<long long> pop;        // population of each city

int fullMask;                 // (1<<n)-1
vector<long long> popSum;     // popSum[mask] = sum of pop[i] for i in mask
vector<int> neighMask;        // neighMask[mask] = neighbors of mask, excluding mask itself

vector<int> pow3;             // pow3[i] = 3^i
vector<int> pow3Subset;       // pow3Subset[mask] = sum(3^i) for i in mask

vector<long long> dpA, dpB;   // dp tables for "A to move" and "B to move"

/*
  Recurrence:
    who=0 => A to move (maximize pop(A)-pop(B))
    who=1 => B to move (minimize pop(A)-pop(B))
  Inputs:
    A, B : disjoint bitmasks of owned cities
    idx  : ternary encoding of ownership of all cities
*/
long long solveState(int A, int B, int idx, int who) {
    long long &memo = (who == 0 ? dpA[idx] : dpB[idx]);
    long long sent  = (who == 0 ? SENT_A : SENT_B);
    if (memo != sent) return memo;

    int freeMask = fullMask ^ A ^ B;            // cities not owned by A or B
    long long terminal = popSum[A] - popSum[B]; // score if game ends now

    // If no free cities remain, nobody can conquer anything.
    if (freeMask == 0) return memo = terminal;

    bool hasMoveSelf = false;   // current player has at least one legal move
    bool hasMoveOther = false;  // opponent has at least one legal move (for pass logic)

    long long best = sent;      // max for A, min for B

    // Enumerate all non-empty submasks C of freeMask.
    for (int C = freeMask; C; C = (C - 1) & freeMask) {
        long long pa = popSum[neighMask[C] & A];
        long long pb = popSum[neighMask[C] & B];
        long long pc = popSum[C];

        bool aValid = (pa > pc + pb);
        bool bValid = (pb > pc + pa);

        if (who == 0) { // A's turn: maximize
            if (aValid) {
                hasMoveSelf = true;
                int nA = A | C;
                int nB = B;
                int nIdx = idx + pow3Subset[C]; // free(0) -> A(1)
                long long v = solveState(nA, nB, nIdx, 1);
                if (v > best) best = v;
            }
            if (bValid) hasMoveOther = true;
        } else {        // B's turn: minimize
            if (bValid) {
                hasMoveSelf = true;
                int nA = A;
                int nB = B | C;
                int nIdx = idx + 2 * pow3Subset[C]; // free(0) -> B(2)
                long long v = solveState(nA, nB, nIdx, 0);
                if (v < best) best = v;
            }
            if (aValid) hasMoveOther = true;
        }
    }

    // If current player can move, they choose the best (minimax).
    if (hasMoveSelf) return memo = best;

    // If neither player can move, game ends here.
    if (!hasMoveOther) return memo = terminal;

    // Otherwise current player must pass.
    return memo = solveState(A, B, idx, who ^ 1);
}

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

    cin >> n >> s >> t;
    --s; --t;

    vector<string> grid(n);
    for (int i = 0; i < n; i++) cin >> grid[i];

    adj.assign(n, 0);
    for (int i = 0; i < n; i++) {
        int m = 0;
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') m |= (1 << j);
        }
        adj[i] = m;
    }

    pop.assign(n, 0);
    for (int i = 0; i < n; i++) cin >> pop[i];

    fullMask = (1 << n) - 1;
    int M = 1 << n;

    // Precompute popSum[mask]
    popSum.assign(M, 0);
    for (int mask = 1; mask < M; mask++) {
        int b = __builtin_ctz(mask); // index of lowest set bit
        popSum[mask] = popSum[mask ^ (1 << b)] + pop[b];
    }

    // Precompute neighMask[mask]
    neighMask.assign(M, 0);
    for (int mask = 0; mask < M; mask++) {
        int nb = 0;
        int x = mask;
        while (x) {
            int b = __builtin_ctz(x);
            x &= (x - 1);
            nb |= adj[b];
        }
        neighMask[mask] = nb & ~mask; // remove nodes inside mask
    }

    // Precompute pow3 and pow3Subset
    pow3.assign(n + 1, 1);
    for (int i = 1; i <= n; i++) pow3[i] = pow3[i - 1] * 3;

    pow3Subset.assign(M, 0);
    for (int mask = 1; mask < M; mask++) {
        int b = __builtin_ctz(mask);
        pow3Subset[mask] = pow3Subset[mask ^ (1 << b)] + pow3[b];
    }

    // DP arrays sized by 3^n
    dpA.assign(pow3[n], SENT_A);
    dpB.assign(pow3[n], SENT_B);

    // Initial state: A owns s, B owns t, A moves first.
    int A0 = 1 << s;
    int B0 = 1 << t;
    int idx0 = pow3[s] + 2 * pow3[t];

    cout << solveState(A0, B0, idx0, 0) << "\n";
    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys
sys.setrecursionlimit(10**7)

def solve():
    input = sys.stdin.readline

    n, s, t = map(int, input().split())
    s -= 1
    t -= 1

    grid = [input().strip() for _ in range(n)]
    pop = list(map(int, input().split()))

    # Build adjacency bitmasks
    adj = [0] * n
    for i in range(n):
        m = 0
        for j, ch in enumerate(grid[i]):
            if ch == '1':
                m |= 1 << j
        adj[i] = m

    full = (1 << n) - 1
    M = 1 << n

    # popSum[mask] = sum of populations for cities in mask
    popSum = [0] * M
    for mask in range(1, M):
        lb = mask & -mask
        i = lb.bit_length() - 1
        popSum[mask] = popSum[mask ^ lb] + pop[i]

    # neighMask[mask] = union of neighbors of nodes in mask, excluding mask
    neighMask = [0] * M
    for mask in range(M):
        nb = 0
        x = mask
        while x:
            lb = x & -x
            i = lb.bit_length() - 1
            x ^= lb
            nb |= adj[i]
        neighMask[mask] = nb & ~mask

    # pow3[i] = 3^i
    pow3 = [1] * (n + 1)
    for i in range(1, n + 1):
        pow3[i] = pow3[i - 1] * 3

    # pow3Subset[mask] = sum(3^i) for i in mask
    pow3Subset = [0] * M
    for mask in range(1, M):
        lb = mask & -mask
        i = lb.bit_length() - 1
        pow3Subset[mask] = pow3Subset[mask ^ lb] + pow3[i]

    # DP over ternary states; separate arrays for whose turn it is
    SENT_A = -(1 << 60)
    SENT_B = +(1 << 60)
    dpA = [SENT_A] * pow3[n]  # A to move
    dpB = [SENT_B] * pow3[n]  # B to move

    def rec(A: int, B: int, idx: int, who: int) -> int:
        """
        Returns optimal final score pop(A)-pop(B) from current state.
        who = 0: A to move (maximize)
        who = 1: B to move (minimize)
        """
        if who == 0:
            if dpA[idx] != SENT_A:
                return dpA[idx]
        else:
            if dpB[idx] != SENT_B:
                return dpB[idx]

        free = full ^ A ^ B
        terminal = popSum[A] - popSum[B]
        if free == 0:
            if who == 0:
                dpA[idx] = terminal
            else:
                dpB[idx] = terminal
            return terminal

        has_self = False
        has_other = False
        best = SENT_A if who == 0 else SENT_B

        c = free
        while c:
            pa = popSum[neighMask[c] & A]
            pb = popSum[neighMask[c] & B]
            pc = popSum[c]

            a_valid = (pa > pc + pb)
            b_valid = (pb > pc + pa)

            if who == 0:
                if a_valid:
                    has_self = True
                    val = rec(A | c, B, idx + pow3Subset[c], 1)
                    if val > best:
                        best = val
                if b_valid:
                    has_other = True
            else:
                if b_valid:
                    has_self = True
                    val = rec(A, B | c, idx + 2 * pow3Subset[c], 0)
                    if val < best:
                        best = val
                if a_valid:
                    has_other = True

            c = (c - 1) & free

        if has_self:
            if who == 0:
                dpA[idx] = best
            else:
                dpB[idx] = best
            return best

        if not has_other:
            # neither can move
            if who == 0:
                dpA[idx] = terminal
            else:
                dpB[idx] = terminal
            return terminal

        # pass
        val = rec(A, B, idx, who ^ 1)
        if who == 0:
            dpA[idx] = val
        else:
            dpB[idx] = val
        return val

    A0 = 1 << s
    B0 = 1 << t
    idx0 = pow3[s] + 2 * pow3[t]  # ternary digits: s -> 1, t -> 2
    ans = rec(A0, B0, idx0, 0)
    print(ans)

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

