A farm has M locked pig pens, each initially containing a certain number of pigs. A worker named Milk needs to sell pigs to N customers who arrive sequentially. Each customer holds keys to some pens and wants to buy a specific number of pigs.

The worker can open any pen that a cutsomer has access to and select pigs for sale. Additionally, he may redistribute pigs within those open pens before closing them. The goal is to maximize the total number of pigs sold throughout the day.

Input Format

• First line: two integers M (number of pens) and N (number of customers)
• Second line: M integers representing initial pig counts per pen
• Next N lines: for each customer:
  • First integer A: number of pens they can access
  • A integers: pen numbers they have keeys to
  • Last integer B: number of pigs they want to purchase

Output Format

Output the maximum number of pigs that can be sold.

Solution Approach

This problem is modeled using a layered graph and maximum flow algorithm. We construct a flow network where:

1. A source node connects to each customer with capacity equal to the initial pig count in accessible pens
2. Each customer connects to the sink with capacity equal to their desired pig count
3. Between customers, we model the temporal order and redistribution via edges with infinite capacity

The key insight is to represent the temporal sequence by connecting previous customers to current ones through shared pens, ensuring that pig redistribution respects the order of arrival.

We use Dinic's algorithm to compute the maximum flow from source to sink.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

typedef long long ll;
const int MAXN = 110;
const int MAXM = 20000;
const int INF = 0x3f3f3f3f;

int m, n, source, sink;
int head[MAXN], edge[MAXM], flow[MAXM], next_edge[MAXM], idx;
int level[MAXN], work[MAXN];
int initial_pig_count[1005];
int last_customer[1005];

void add_edge(int u, int v, int cap) {
    edge[idx] = v; flow[idx] = cap; next_edge[idx] = head[u]; head[u] = idx++;
    edge[idx] = u; flow[idx] = 0; next_edge[idx] = head[v]; head[v] = idx++;
}

bool bfs() {
    memset(level, -1, sizeof(level));
    queue<int> q;
    q.push(source);
    level[source] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i != -1; i = next_edge[i]) {
            int v = edge[i];
            if (level[v] == -1 && flow[i] > 0) {
                level[v] = level[u] + 1;
                q.push(v);
            }
        }
    }
    return level[sink] != -1;
}

int dfs(int u, int limit) {
    if (u == sink) return limit;
    int flow = 0;
    for (int& i = work[u]; i != -1 && flow < limit; i = next_edge[i]) {
        int v = edge[i];
        if (level[v] == level[u] + 1 && flow[i] > 0) {
            int t = dfs(v, min(flow[i], limit - flow));
            if (t == 0) level[v] = -1;
            flow[i] -= t;
            flow[i^1] += t;
            flow += t;
        }
    }
    return flow;
}

int max_flow() {
    int result = 0;
    while (bfs()) {
        memcpy(work, head, sizeof(head));
        result += dfs(source, INF);
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> m >> n;
    memset(head, -1, sizeof(head));
    source = 0;
    sink = n + 1;
    
    for (int i = 1; i <= m; ++i) {
        cin >> initial_pig_count[i];
    }
    
    for (int i = 1; i <= n; ++i) {
        int key_count;
        cin >> key_count;
        for (int j = 0; j < key_count; ++j) {
            int pen;
            cin >> pen;
            if (last_customer[pen]) {
                add_edge(last_customer[pen], i, INF);
            } else {
                add_edge(source, i, initial_pig_count[pen]);
            }
            last_customer[pen] = i;
        }
        int demand;
        cin >> demand;
        add_edge(i, sink, demand);
    }
    
    cout << max_flow() << endl;
    return 0;
}