## 1) Concise, abridged problem statement

You need to inflate **M** balloons using **one** balloon-filling device that can be operated by **at most one volunteer per minute**.
There are **N** volunteers. If volunteer *i* works for one minute, they inflate **Ai** balloons, and then must rest for **Bi** minutes before they can work again.
Find the **minimum number of minutes** needed to inflate at least **M** balloons (or output `-1` if impossible).

Constraints: `1 ≤ M ≤ 100`, `1 ≤ N ≤ 10`, `0 ≤ Ai ≤ 10`, `1 ≤ Bi ≤ 4`.

---

## 2) Detailed editorial (solution explanation)

### Key observations

- Time proceeds in **whole minutes**.
- Each minute, you either:
  1) assign **one available volunteer** to work, producing `Ai` balloons, then that volunteer enters cooldown for `Bi` minutes, while everyone else's cooldown (if any) decreases by 1, or
  2) if **nobody is available**, the device sits idle and only cooldown timers tick down by 1.

So this is a shortest-time problem on states.

### Naive DP state is too large
If we store cooldown time for every volunteer, we'd have up to `5^N` combinations (because cooldown remaining is 0..4), which is too big in the worst case.

### Crucial constraint: `Bi ≤ 4` implies sparsity
A volunteer's cooldown is at most 4, and cooldown decreases by 1 each minute.
That means at any moment, the number of volunteers with **positive** cooldown is limited:

- A volunteer set to cooldown `Bi` stays positive for `Bi` minutes.
- With `Bi ≤ 4`, each "used" volunteer disappears from the positive set quickly.
- In fact, the solution leverages the known bound that at most **4 volunteers** need to be tracked as "currently resting" in an optimal state representation, and enumerates only those subsets.

The provided code explicitly enumerates all subsets of volunteers of size ≤ 4 and stores cooldowns only for those volunteers; everyone not in the subset is assumed to have cooldown 0 (available).

### State representation

We maintain:
- `bal` = balloons still needed (clamped to `[0..M]`)
- a subset `S` of volunteers currently resting (|S| ≤ 4)
- for each volunteer in `S`, an integer `rest[i]` in `{1,2,3,4}` = minutes remaining until available

To make this fast, the subset `S` is represented by an index `ci` into a precomputed list `combos[ci] = positions`, and the remaining times are packed into an integer `v` using 2 bits per person (since 1..4 fits in 2 bits after subtracting 1).

So the BFS/DP state is `(bal, ci, v)`.

### Transitions (one minute step)

From a state, define the set of **available volunteers**:
- those not currently in `S` (i.e., `rest[i] == 0`) and with `Ai > 0` (using someone with `Ai=0` is never helpful).

Two cases:

1) **At least one available volunteer exists**
   Choose one such volunteer `i` to work this minute:
   - balloons decrease: `bal' = max(0, bal - Ai)`
   - cooldowns tick down for everyone currently resting: `rest[j] = max(0, rest[j]-1)`
   - chosen volunteer gets reset: `rest[i] = Bi`
   - recompute the new resting subset `S' = { i | rest[i] > 0 }` (still size ≤ 4), encode to `(ci', v')`.

2) **No available volunteer exists**
   Device idles:
   - balloons unchanged
   - all cooldowns tick down by 1
   - recompute subset and encode

Each transition costs exactly **1 minute**, so we want the shortest number of steps to reach `bal=0`. That's exactly BFS on an unweighted graph.

### Why precompute a graph?
The transitions on `(ci, v)` do **not** depend on `bal` (only the balloon decrement does).
So we can precompute:
- `available[ci][v]`: list of volunteers that can be used now
- `adj[ci][v][used]`: the resulting `(ci', v')` if we either idle (`used = -1`) or use volunteer `used`.

Then BFS over `(bal, ci, v)` is fast enough.

### Complexity
- Number of subsets of size ≤ 4 among N≤10 is:
  \[
  \sum_{k=0}^4 \binom{10}{k} = 386
  \]
- For each subset size `k`, there are `4^k ≤ 256` cooldown configurations.
So `(ci, v)` combinations are at most about `386 * 256 ≈ 98k`.

BFS adds a factor `(M+1) ≤ 101`, so around `~10 million` states worst-case, but actual reachable states are typically much fewer; with tight precompute and O(1) transitions it fits.

---

## 3) C++ Solution

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int m, n;
vector<int> a, b;

void read() {
    cin >> m >> n;
    a.resize(n);
    b.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }
}

vector<vector<int>> combos;
vector<int> combo_index;

vector<vector<vector<int>>> available;
vector<vector<vector<pair<int, int>>>> adj;

int encode_state(const vector<int>& rest, const vector<int>& positions) {
    int v = 0;
    for(int i = 0; i < (int)positions.size(); i++) {
        v |= (rest[positions[i]] - 1) << (2 * i);
    }
    return v;
}

void decode_state(int v, const vector<int>& positions, vector<int>& rest) {
    fill(rest.begin(), rest.end(), 0);
    for(int i = 0; i < (int)positions.size(); i++) {
        rest[positions[i]] = ((v >> (2 * i)) & 3) + 1;
    }
}

void build_graph() {
    combo_index.assign(1 << n, -1);
    for(int mask = 0; mask < (1 << n); mask++) {
        if(__builtin_popcount(mask) <= 4) {
            combo_index[mask] = combos.size();
            vector<int> positions;
            for(int i = 0; i < n; i++) {
                if(mask & (1 << i)) {
                    positions.push_back(i);
                }
            }
            combos.push_back(positions);
        }
    }

    int num_combos = combos.size();
    available.assign(num_combos, vector<vector<int>>(256));
    adj.assign(
        num_combos,
        vector<vector<pair<int, int>>>(256, vector<pair<int, int>>(n + 1))
    );

    for(int ci = 0; ci < num_combos; ci++) {
        int sz = combos[ci].size();
        int max_v = 1 << (2 * sz);

        for(int v = 0; v < max_v; v++) {
            vector<int> rest(n, 0);
            decode_state(v, combos[ci], rest);

            for(int i = 0; i < n; i++) {
                if(rest[i] == 0 && a[i] > 0) {
                    available[ci][v].push_back(i);
                }
            }

            for(int used = -1; used < n; used++) {
                vector<int> new_rest(n);
                for(int i = 0; i < n; i++) {
                    if(i == used) {
                        new_rest[i] = b[i];
                    } else {
                        new_rest[i] = max(0, rest[i] - 1);
                    }
                }

                int new_mask = 0;
                for(int i = 0; i < n; i++) {
                    if(new_rest[i] > 0) {
                        new_mask |= (1 << i);
                    }
                }
                int new_ci = combo_index[new_mask];
                int new_v = encode_state(new_rest, combos[new_ci]);

                adj[ci][v][used + 1] = {new_ci, new_v};
            }
        }
    }
}

void solve() {
    // The solution is fairly simple - we can simply do a dynamic programming
    // dp[balloons left][state of time left]. The second dimension represents
    // the time left for every volunteer until it can fill a balloon again. On
    // first glance, this would be too slow as we might have O(MAX_B^N) states,
    // but in reality we can have at most 4 people with non-zero time left.
    // We have C(10, 4) = 210 (although we need to account for smaller sets
    // too), and very naively there are 4^4 = 256 combinations for their wait
    // times, meaning we are around a few million states.
    //
    // We might have to be a bit careful with time limits, where a good way is
    // to notice that the transitions don't depend on "balloons left", so we can
    // precompute the graph based on the other two dimensions. Then we can do a
    // BFS on this graph.

    build_graph();

    int num_combos = combos.size();
    vector<vector<vector<int>>> dist(
        m + 1, vector<vector<int>>(num_combos, vector<int>(256, -1))
    );

    queue<tuple<int, int, int>> q;
    dist[m][0][0] = 0;
    q.push({m, 0, 0});

    while(!q.empty()) {
        auto [bal, ci, v] = q.front();
        q.pop();

        if(bal == 0) {
            cout << dist[bal][ci][v] << '\n';
            return;
        }

        int d = dist[bal][ci][v];
        const auto& avail = available[ci][v];

        if(avail.empty()) {
            auto [new_ci, new_v] = adj[ci][v][0];
            if(dist[bal][new_ci][new_v] == -1) {
                dist[bal][new_ci][new_v] = d + 1;
                q.push({bal, new_ci, new_v});
            }
        } else {
            for(int i: avail) {
                auto [new_ci, new_v] = adj[ci][v][i + 1];
                int new_bal = max(0, bal - a[i]);
                if(dist[new_bal][new_ci][new_v] == -1) {
                    dist[new_bal][new_ci][new_v] = d + 1;
                    q.push({new_bal, new_ci, new_v});
                }
            }
        }
    }

    cout << -1 << '\n';
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 4) Python solution (same approach) with detailed comments

```python
import sys
from collections import deque

def solve() -> None:
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    M = int(next(it))
    N = int(next(it))
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i] = int(next(it))
        B[i] = int(next(it))

    # If nobody can produce balloons, impossible unless M==0 (but M>=1).
    if all(a == 0 for a in A):
        print(-1)
        return

    # ---- Precompute combos (subsets of size <= 4) and mapping mask -> combo index ----
    combos = []                 # combos[ci] = list of indices in the subset
    combo_index = [-1] * (1 << N)

    for mask in range(1 << N):
        if mask.bit_count() <= 4:
            combo_index[mask] = len(combos)
            positions = [i for i in range(N) if (mask >> i) & 1]
            combos.append(positions)

    num_combos = len(combos)

    # Encode/decode rest times for indices in positions using 2 bits each.
    # Stored value is (rest-1) in 0..3.
    def encode_state(rest, positions):
        v = 0
        for j, idx in enumerate(positions):
            v |= (rest[idx] - 1) << (2 * j)
        return v

    def decode_state(v, positions):
        rest = [0] * N
        for j, idx in enumerate(positions):
            rest[idx] = ((v >> (2 * j)) & 3) + 1
        return rest

    # available[ci][v] = list of usable volunteers when in (ci,v)
    available = [[[] for _ in range(256)] for __ in range(num_combos)]
    # adj[ci][v][used+1] -> (new_ci,new_v), used=-1 means idle
    adj = [[[None] * (N + 1) for _ in range(256)] for __ in range(num_combos)]

    # Build transitions for each (ci,v) that is valid for that combo size
    for ci in range(num_combos):
        positions = combos[ci]
        sz = len(positions)
        max_v = 1 << (2 * sz)   # equals 4^sz

        for v in range(max_v):
            rest = decode_state(v, positions)

            # Determine available volunteers (not resting and A[i]>0)
            avail = []
            for i in range(N):
                if rest[i] == 0 and A[i] > 0:
                    avail.append(i)
            available[ci][v] = avail

            # Precompute transitions for idle and for using each volunteer
            for used in range(-1, N):
                new_rest = [0] * N
                for i in range(N):
                    if i == used:
                        new_rest[i] = B[i]        # used volunteer starts cooldown
                    else:
                        new_rest[i] = rest[i] - 1 # time passes
                        if new_rest[i] < 0:
                            new_rest[i] = 0

                new_mask = 0
                for i in range(N):
                    if new_rest[i] > 0:
                        new_mask |= 1 << i

                new_ci = combo_index[new_mask]
                # new_mask must be size <= 4 for reachable states in this modeling
                # (the intended solution relies on that property).
                new_v = encode_state(new_rest, combos[new_ci])
                adj[ci][v][used + 1] = (new_ci, new_v)

        # For v >= max_v, (ci,v) is not a valid encoding; we leave as defaults.
        # BFS will never generate them.

    # ---- BFS over (balloons_left, ci, v) with unit cost per minute ----
    # dist[bal][ci][v] = minutes, use -1 for unvisited
    dist = [[[-1] * 256 for _ in range(num_combos)] for __ in range(M + 1)]

    q = deque()
    dist[M][0][0] = 0
    q.append((M, 0, 0))

    while q:
        bal, ci, v = q.popleft()
        d = dist[bal][ci][v]

        if bal == 0:
            print(d)
            return

        avail = available[ci][v]
        if not avail:
            # Must idle
            new_ci, new_v = adj[ci][v][0]
            if dist[bal][new_ci][new_v] == -1:
                dist[bal][new_ci][new_v] = d + 1
                q.append((bal, new_ci, new_v))
        else:
            # Try using each available volunteer
            for i in avail:
                new_ci, new_v = adj[ci][v][i + 1]
                new_bal = bal - A[i]
                if new_bal < 0:
                    new_bal = 0
                if dist[new_bal][new_ci][new_v] == -1:
                    dist[new_bal][new_ci][new_v] = d + 1
                    q.append((new_bal, new_ci, new_v))

    print(-1)

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

---

## 5) Compressed editorial

Model each minute as a BFS step in an unweighted state graph. A state is `(bal, cooldowns)` where `bal` is balloons still needed, and `cooldowns[i]` is minutes until volunteer `i` can work again. Directly this is huge, but since `Bi ≤ 4`, we only need to explicitly store volunteers with positive cooldown, and in reachable states there are at most 4 of them. Enumerate all subsets of volunteers of size ≤ 4 and encode their cooldowns with 2 bits each (values 1..4). Precompute, for every `(subset, encoded_times)`, which volunteers are available and what the next `(subset, encoded_times)` becomes after idling or using a volunteer. Then BFS over `(bal, subset, encoded_times)` with transitions costing 1 minute; when `bal==0` output distance, else `-1` if unreachable.
