Bazaar Bidding

They landed on Earth on the morning of Eid el-Fitr. The circuit board was patched just in time, the shields held through reentry, and the rocket touched down on Algerian soil. The smell of Me9rot elouz drifted from every kitchen. Children in crisp new clothes ran between houses collecting Eidi money. Saha Aidkoum echoed from every doorstep. The crew stepped out into sunlight for the first time in weeks and scattered to find their families.

That afternoon, the neighborhood bazaar was in full swing. Vendors lined both sides of the street with trays of Me9rot elouz, boxes of pastries, and steaming pots of mint tea. Children darted between stalls clutching their Eidi money. The bazaar organizer was overwhelmed. Dozens of bids were coming in for bundles of items, some overlapping, some with exclusivity clauses, some dependent on other bids being accepted, and every time bids crossed categories there was a penalty to pay. Someone needed to figure out which bids to accept to maximize the net revenue.

Adel sat down at the organizer's table. The crew gathered around. One last problem before the day was done.

Input Format

• Line 1: N B C where N is the number of items, B is the number of bids, and C is the number of categories.
• Line 2: cat_0 cat_1 ... cat_{N-1}, the category of each item (0-indexed), space-separated.
• Lines 3 to B+2: Each line defines one bid: price item_1 item_2 ... item_k | exc_1 exc_2 ... > dep_1 dep_2 ...
  • price is a positive integer (the bid amount).
  • item_1 item_2 ... item_k are the item IDs this bid wants (0-indexed).
  • After the | separator: a (possibly empty) list of bid IDs that are excluded if this bid wins.
  • After the > separator: a (possibly empty) list of bid IDs that must also be winning for this bid to be eligible (dependencies).
• Lines B+3 to B+2+C^2: The penalty matrix, C lines of C space-separated integers. Entry pen[a][b] is the penalty when a winning bid touches category a and another winning bid touches category b.
• Line B+3+C^2: Q, the number of modification queries for Part 2.
• Lines B+4+C^2 to end: One query per line (see Part 2 for formats).

N <= 300, B <= 500, C <= 40. Q <= 700. All prices and penalties are non-negative integers. Dependencies form a DAG (no cycles).

Find the subset of winning bids that maximizes the score:

score = sum(winner prices) - sum(penalties for every pair of winners)

Hard Constraints

1. No item overlap: Two winning bids cannot share any item.
2. Exclusivity: If bid X wins and bid Y is in X's exclusivity list, then bid Y cannot win.
3. Dependencies: If bid X is in the winning set and X's dependency list contains bid Y, then bid Y must also be in the winning set. This applies transitively.

Penalty Computation (Soft Constraint)

For every pair of winning bids (A, B), compute their cross-category penalty:

1. Find all categories touched by bid A's items.
2. Find all categories touched by bid B's items.
3. For every pair (catA, catB) from those two sets, add pen[catA][catB].

The total penalty is the sum over all pairs of winners. The penalty is computed over every pair of winning bids, not within a single bid.

Output: The maximum achievable score as a single integer.

Example Input

8 6 2
0 0 0 0 1 1 1 1
10 0 1 | >
8 2 3 | > 0
15 4 5 | > 0 1
20 0 4 | >
6 6 7 | 3 > 1
12 2 6 | >
0 3
3 0
3
B 2
A 3
K 2

Example Walkthrough

Checking winners {bid 0, bid 1, bid 2}:

Step 1: Legality.

• Item conflicts: {0,1} intersect {2,3} = empty, {0,1} intersect {4,5} = empty, {2,3} intersect {4,5} = empty. No overlap.
• Exclusivity: none of these bids exclude each other.
• Dependencies: bid 0 needs nothing. Bid 1 needs bid 0 (present). Bid 2 needs bid 0 and bid 1 (both present).

Step 2: Penalty.

bid 0 touches: items {0,1} -> categories {0} bid 1 touches: items {2,3} -> categories {0} bid 2 touches: items {4,5} -> categories {1} bid 0 vs bid 1: (cat 0, cat 0) = 0 bid 0 vs bid 2: (cat 0, cat 1) = 3 bid 1 vs bid 2: (cat 0, cat 1) = 3 Total penalty = 6

Step 3: Score = 10 + 8 + 15 - 6 = 27.

The optimal score for the example is 27. Finding which bids achieve it is the challenge.

What is the maximum auction score?