Overview

This is a problem where you cannot simultaneously select sections that are directly connected by corridors (independent set constraint), and you must maximize the total capacity of selected sections, then cap the result at \(M\).

Analysis

• The condition “selected sections are not connected by edges” is what graph theory calls an independent set.
  Thus the essence is finding the maximum weight independent set (where each vertex has weight \(P_i\)), and finally taking \(\min(\cdot, M)\) so it doesn’t exceed \(M\).

• Naively trying “all subsets” gives \(2^N\) possibilities, and even for \(N \le 40\),
  \(2^{40} \approx 10^{12}\), which is far too slow (TLE).

• Given the constraint \(N \le 40\), we use the classic technique Meet-in-the-Middle.
  We split the vertices into a first half \(A\) and a second half \(B\). Each half has at most 20 vertices, so the enumeration drops to about \(2^{20} \approx 10^6\).

• However, depending on the choice in \(A\), the “vertices in \(B\) that cannot be selected (those connected to \(A\) by edges)” change.
  To handle this efficiently, we precompute on the \(B\) side “the maximum weight of an independent set that can be formed from the allowed vertex set (mask).”

Algorithm

Below, we split the vertex set into the first half \(A\) (size \(n_1\)) and the second half \(B\) (size \(n_2\)), where \(n_1=\lfloor N/2\rfloor\).

1. Represent the graph with bitmasks

• For each vertex \(i\), store the adjacency set as a bitmask adj[i].
• Prepare adjacency within \(A\) (adjA[i]), adjacency within \(B\) (adjB[j]), and which vertices in \(B\) each vertex in \(A\) connects to (crossA[i]).

2. Full enumeration of the second half \(B\): independent set weights weightB

• For each subset \(m\) of \(B\) (\(0 \le m < 2^{n_2}\)), compute:
  • weightB[m] = -1 (impossible) or the total capacity if it’s an independent set, using a DP approach.
• Method: Take the lowest set bit lsb of \(m\), and check whether vertex \(v\) can be added:
  • The previous set prev = m ^ lsb is independent, and
  • \(v\) is not adjacent to any vertex in prev ((adjB[v] & prev) == 0). If so, weightB[m] = weightB[prev] + P[v].

3. Build “maximum value within an allowed set” (subset DP)

Since the “allowed vertex set in \(B\)” changes with each choice of \(A\), we build the following:

• best[mask] = “the maximum weight among subsets of mask that form an independent set”

Procedure: 1. First, set best[m] = max(best[m], weightB[m]) (only independent sets have positive values). 2. Then perform the classic subset DP:
propagate best[mask] = max(best[mask], best[mask without one bit]) for all bits.
This allows best[allowed] to be retrieved in \(O(1)\) for any allowed.

4. Full enumeration of the first half \(A\): independent sets and “forbidden set on \(B\) side”

• For each subset \(m\) of \(A\):
  • weightA[m] = total capacity if independent within \(A\), otherwise -1
  • forb[m] = the set of vertices on the \(B\) side connected by edges to vertices in \(m\) (bitmask) are computed similarly via DP.
• If \(m\) is independent, the usable set on the \(B\) side is
  allowed = allB ^ forb[m] (allB is the mask of all vertices in \(B\)),
  and the maximum total is
  $\( \text{weightA}[m] + \text{best}[\text{allowed}] \)$

5. Cap with \(M\) at the end

As stated in the problem, the total storage cannot exceed \(M\), so the answer is $\( \min(\text{maximum capacity sum},\, M) \)$

Complexity

• Time complexity:
  
  • Independent set DP for \(B\): \(O(2^{n_2})\) (constant bit operations per state)
    
  • Subset DP: \(O(n_2 \cdot 2^{n_2})\)
    
  • DP for \(A\) and combining: \(O(2^{n_1})\)
    Overall:
    $\( O\big((n_2+1)2^{n_2} + 2^{n_1}\big) = O\big(N \cdot 2^{N/2}\big) \)$
• Space complexity:
  weightB, best are \(O(2^{n_2})\), and weightA, forb are \(O(2^{n_1})\), so
  $\( O(2^{N/2}) \)$

Implementation Tips

• Using bitmasks for adjacency allows the “is there an adjacency?” check to be done in a single operation (adj[v] & subset) == 0, which is fast.

• Rebuilding best[allowed] each time would be too slow, so precompute with subset DP for \(O(1)\) lookup.

• In Python, since arrays can become large, using memory-efficient array('q') (64-bit integers) or array('I') (32-bit) instead of list provides more stability.

• Reading input with sys.stdin.buffer.read() all at once and iterating over it is faster.

  Source Code

import sys
from array import array

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    M = next(it)
    K = next(it)
    P = [next(it) for _ in range(N)]

    adj = [0] * N
    for _ in range(K):
        u = next(it) - 1
        v = next(it) - 1
        adj[u] |= 1 << v
        adj[v] |= 1 << u

    n1 = N // 2
    n2 = N - n1
    maskA = (1 << n1) - 1
    maskB = (1 << n2) - 1

    PA = P[:n1]
    PB = P[n1:]

    adjA = [0] * n1
    crossA = [0] * n1
    for i in range(n1):
        a = adj[i]
        adjA[i] = a & maskA
        crossA[i] = (a >> n1) & maskB

    adjB = [0] * n2
    for j in range(n2):
        orig = n1 + j
        adjB[j] = (adj[orig] >> n1) & maskB

    sizeB = 1 << n2
    weightB = array('q', [-1]) * sizeB
    weightB[0] = 0
    for m in range(1, sizeB):
        lsb = m & -m
        v = lsb.bit_length() - 1
        prev = m ^ lsb
        w = weightB[prev]
        if w >= 0 and (adjB[v] & prev) == 0:
            weightB[m] = w + PB[v]

    best = array('q', [0]) * sizeB
    for m in range(sizeB):
        w = weightB[m]
        if w > 0:
            best[m] = w

    for i in range(n2):
        bit = 1 << i
        for m in range(sizeB):
            if m & bit:
                other = m ^ bit
                bo = best[other]
                if bo > best[m]:
                    best[m] = bo

    sizeA = 1 << n1
    weightA = array('q', [-1]) * sizeA
    forb = array('I', [0]) * sizeA
    weightA[0] = 0
    for m in range(1, sizeA):
        lsb = m & -m
        v = lsb.bit_length() - 1
        prev = m ^ lsb
        w = weightA[prev]
        if w >= 0 and (adjA[v] & prev) == 0:
            weightA[m] = w + PA[v]
            forb[m] = forb[prev] | crossA[v]

    ans = 0
    allB = maskB
    for m in range(sizeA):
        w = weightA[m]
        if w >= 0:
            allowed = allB ^ forb[m]
            total = w + best[allowed]
            if total > ans:
                ans = total

    if ans > M:
        ans = M
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.