<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

256. Balloons
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



Due to the preparation to the wedding you have to fill up M balloons. There are N volunteers and one device for balloons filling up. Device can fill at most one balloon at a time. Each volunteer can continuously operate the device for 1 minute.
Volunteer number i can fill Ai balloons during one minute and then he or she must have at least Bi minutes of rest.
You are to write a program that computes minimal possible time of filling up M balloons.

Input
There are two integers M and N on the first line (1 <= M <= 100, 1 <= N <= 10).
Next N lines contain two integers each: Ai and Bi (0 <= Ai <= 10, 1 <= Bi <= 4).

Output
Print one integer T - the minimal number of minutes required to filling M balloons.

Sample test(s)

Input
10 3
4 4
3 4
2 3

Output
5
Author:	Andrew V. Lazarev
Resource:	Saratov SU Contest: Golden Fall 2004
Date:	October 2, 2004

<|response|>
## 1) Abridged problem statement (concise)

You must inflate **M** balloons using **one** pump that can be operated by **at most one volunteer per minute**.
There are **N** volunteers. If volunteer `i` operates the pump for **1 minute**, they inflate `Ai` balloons, then must **rest** for `Bi` minutes before they can work again. (`Bi ≤ 4`)

Find the **minimum number of whole minutes** needed to inflate at least **M** balloons (output `-1` if impossible).

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

---

## 2) Key observations

1. **Time is discrete (minutes)** and each minute has exactly one action:
   - pick one currently-available volunteer to work, or
   - if nobody is available, the pump is idle.

2. After each minute, **all cooldown timers decrease by 1** (to a minimum of 0).
   If volunteer `i` works, their timer becomes exactly `Bi` at the end of that minute.

3. This is a **shortest path / BFS** problem:
   - Each "minute" is an edge of cost 1.
   - We want the shortest time to reach "balloons remaining = 0".

4. Naively storing cooldown for all volunteers yields up to `5^N` states, but we can exploit:
   - `Bi ≤ 4`, so each cooldown is in `{0,1,2,3,4}`.
   - We store **only volunteers with positive cooldown** ("currently resting"), encode them compactly, and enumerate only subsets of size ≤ 4 (as used in the reference solution).

5. Volunteers with `Ai = 0` are never useful to pick (they don't reduce remaining balloons), so they can be ignored in "available to work" lists.

---

## 3) Full solution approach

### State model (minute-by-minute)

Let:
- `bal` = balloons still needed (clamped to `0..M`)
- for each volunteer `i`, `rest[i]` = minutes until they can work again (`0` means available)

From a state, in one minute:
- If we choose volunteer `i` with `rest[i]=0`, then:
  - `bal := max(0, bal - Ai)`
  - all other `rest[j] := max(0, rest[j]-1)`
  - `rest[i] := Bi`
- If no volunteer is available, we **must idle**:
  - `bal` unchanged
  - all `rest[j] := max(0, rest[j]-1)`

Each step costs 1 minute ⇒ shortest time is BFS.

### Compressing the cooldown state

We represent only the set of volunteers with `rest>0` as a subset mask `S`.
Because `Bi ≤ 4`, we can encode each positive rest time using **2 bits** (values 1..4).

We precompute:
- All subsets of volunteers of size ≤ 4 (`combos`)
- A mapping `mask -> combo_index`
- For every `(combo_index, encoded_rest_times)`:
  - which volunteers are currently available
  - the resulting `(combo_index', encoded_rest_times')` after:
    - idling
    - using a specific volunteer

This is fast because:
- Number of subsets of size ≤4 out of N≤10 is `Σ C(10,k), k=0..4 = 386`
- For subset size `k`, there are `4^k = 2^(2k) ≤ 256` encodings

### BFS over `(bal, ci, v)`

We run BFS with distance array:
- `dist[bal][ci][v] = minimal minutes to reach this state`

Start:
- `bal = M`
- nobody resting ⇒ empty subset ⇒ `ci = 0` (the empty subset is enumerated first), and `v = 0`

Goal:
- any state with `bal == 0` (first time reached is optimal)

If BFS finishes without reaching `bal=0`, the answer is `-1` (e.g., all `Ai=0`).

---

## 4) C++ implementation

```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;
}
```

---

## 5) Python implementation (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 all Ai are zero, impossible to inflate any positive M
    if all(a == 0 for a in A):
        print(-1)
        return

    # ---- Precompute all subsets of volunteers of size <= 4 ----
    combos = []                 # combos[ci] = list of indices in the subset
    combo_index = [-1] * (1 << N)  # mask -> ci, only valid for popcount<=4

    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)

    C = len(combos)

    # Encode rest times for volunteers in positions as 2 bits each: store (rest-1)
    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  # 0..3 -> 1..4
        return rest

    # available[ci][v] = list of volunteers currently available (rest==0 and A[i]>0)
    available = [[[] for _ in range(256)] for __ in range(C)]
    # adj[ci][v][used+1] = (next_ci, next_v), used=-1 => 0, used=i => i+1
    adj = [[[None] * (N + 1) for _ in range(256)] for __ in range(C)]

    # ---- Precompute transitions for each cooldown-configuration ----
    for ci in range(C):
        positions = combos[ci]
        sz = len(positions)
        max_v = 1 << (2 * sz)  # 4^sz

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

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

            # Transition for idling and for using any volunteer
            for used in range(-1, N):
                new_rest = [0] * N
                for i in range(N):
                    if i == used:
                        new_rest[i] = B[i]
                    else:
                        new_rest[i] = rest[i] - 1
                        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_v = encode_state(new_rest, combos[new_ci])
                adj[ci][v][used + 1] = (new_ci, new_v)

    # ---- BFS over (balloons_left, ci, v) ----
    dist = [[[-1] * 256 for _ in range(C)] for __ in range(M + 1)]
    q = deque()

    start_ci = combo_index[0]  # empty resting set
    dist[M][start_ci][0] = 0
    q.append((M, start_ci, 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
            nci, nv = adj[ci][v][0]  # used=-1
            if dist[bal][nci][nv] == -1:
                dist[bal][nci][nv] = d + 1
                q.append((bal, nci, nv))
        else:
            # Try each available worker
            for i in avail:
                nci, nv = adj[ci][v][i + 1]
                nbal = bal - A[i]
                if nbal < 0:
                    nbal = 0
                if dist[nbal][nci][nv] == -1:
                    dist[nbal][nci][nv] = d + 1
                    q.append((nbal, nci, nv))

    print(-1)

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

The BFS-with-compressed-cooldowns approach above matches the intended constraints and the reference solution style.
