Overview

This problem asks us to maximize profit under two constraints: a budget limitation (an element of the knapsack problem) and pairs of projects that cannot be selected simultaneously (an element of the maximum independent set problem). The key to the solution is that the number of projects \(N\) is very small, at most 18.

Analysis

1. Focus on the Constraints

First, notice the constraint \(N \leq 18\). In general, when \(N\) is 20 or less, brute-force search or exponential-time algorithms using bits (such as \(2^N\)) are likely to be effective.

2. Difference from a Simple Knapsack Problem

If there were no “conflict relationships,” this would be a typical “knapsack problem.” However, since there is a constraint that “projects \(A\) and \(B\) cannot be selected simultaneously,” it is difficult to directly apply standard dynamic programming (DP).

3. Considering Brute-Force Search

There are \(2^N\) possible ways to select projects. When \(N=18\), \(2^{18} = 262,144\). With this number, it is perfectly feasible to examine all combinations. For each combination, we check whether “there are no conflicts” and “the budget is not exceeded,” and find the one with the maximum profit among those that satisfy the conditions.

4. Efficient Search

Instead of simply generating all combinations and then checking them, we can search more efficiently by adding projects one by one and keeping only those combinations where “no conflicts occur.”

Algorithm

We adopt a bit-based dynamic programming approach, or more precisely, a method that incrementally constructs “valid independent sets (sets without conflicts).”

1. Organizing Conflict Relationships: For each project \(i\), we manage which projects with smaller indices conflict with it using a bitmask adj[i].
2. Maintaining Valid Sets: We maintain a list of “conflict-free project combinations (independent sets) discovered so far.” Each element is (bitmask, total cost, total profit).
3. Adding Projects: For each project \(i = 0, 1, \dots, N-1\) in order, we perform the following operations:
   • For all currently maintained “valid sets,” we try adding project \(i\).
   • The conditions for adding are the following two:
     • The projects in the current set do not conflict with project \(i\) (mask & adj[i] == 0).
     • The total cost after adding project \(i\) does not exceed \(K\).
   • If the conditions are met, we add it to the list as a new “valid set.”
4. Updating the Maximum: We check the profit of each newly created set and update the maximum profit found so far.

Complexity

• Time Complexity: \(O(2^N)\) In the worst case (when there are no conflicts at all), the number of valid combinations is \(2^N\). For \(N=18\), this is approximately \(2.6 \times 10^5\), and since the processing at each step is fast, it fits well within the time limit.
• Space Complexity: \(O(2^N)\) Since we store information about valid combinations in a list, we need memory to hold up to \(2^N\) elements.

Implementation Notes

• Utilizing Bit Operations: By representing sets of projects as integers (bitmasks), conflict checking can be performed with the extremely fast bit operation m & adj[i].

• Incremental Updates: The code uses lists masks, costs_list, and profits_list, and each time a new project is considered, new states are appended to the existing lists. This avoids exploring unnecessary states.

  Source Code

import sys

def solve():
    # Read all input at once and split into a list of strings
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Use an iterator to process the input data efficiently
    it = iter(input_data)
    N = int(next(it))
    M = int(next(it))
    K = int(next(it))
    
    costs = []
    profits = []
    for _ in range(N):
        costs.append(int(next(it)))
        profits.append(int(next(it)))
        
    # adj[i] is a bitmask of projects with indices less than i that conflict with project i
    adj = [0] * N
    for _ in range(M):
        u = int(next(it)) - 1
        v = int(next(it)) - 1
        # We only care about conflicts with previously processed projects (index < current i)
        if u < v:
            adj[v] |= (1 << u)
        else:
            adj[u] |= (1 << v)
        
    # We maintain lists of all valid independent sets found so far.
    # Each set is represented by its bitmask, total cost, and total profit.
    masks = [0]
    costs_list = [0]
    profits_list = [0]
    max_profit = 0
    
    # Iterate through each project to decide whether to include it
    for i in range(N):
        c = costs[i]
        p = profits[i]
        a = adj[i]
        
        new_masks = []
        new_costs = []
        new_profits = []
        
        # Try adding project i to all currently known valid independent sets
        for m, c_total, p_total in zip(masks, costs_list, profits_list):
            # Check for conflicts with projects already in the set m
            # and verify if the total cost is within the budget K
            if not (m & a):
                nc = c_total + c
                if nc <= K:
                    np = p_total + p
                    new_masks.append(m | (1 << i))
                    new_costs.append(nc)
                    new_profits.append(np)
                    if np > max_profit:
                        max_profit = np
        
        # Add the newly formed independent sets to our collection
        masks.extend(new_masks)
        costs_list.extend(new_costs)
        profits_list.extend(new_profits)
        
    # Output the maximum profit found
    print(max_profit)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-preview.