<|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 = index(empty)`, and `v = 0`

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

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

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>
using namespace std;

/*
  Problem: minimal minutes to inflate M balloons with:
  - one device, at most 1 volunteer works per minute
  - volunteer i produces Ai balloons in 1 minute, then must rest Bi minutes
  - Bi <= 4, N <= 10, M <= 100

  We do BFS on states:
    (bal, ci, v)
  bal = balloons remaining (0..M)
  ci  = index of subset of resting volunteers (subset size <= 4)
  v   = packed rest times (2 bits per person in that subset), each in 1..4 stored as (t-1).

  Transitions cost 1 minute:
  - if someone available, choose one available volunteer to work
  - else idle
*/

int M, N;
vector<int> A, B;

// combos[ci] = list of volunteer indices in the resting subset for combo-index ci
vector<vector<int>> combos;
// combo_index[mask] = ci for subsets mask with popcount <= 4
vector<int> combo_index;

// available[ci][v] = list of volunteers that are available now (rest==0) and A[i]>0
vector<vector<vector<int>>> available;

// adj[ci][v][used+1] = (next_ci, next_v) after 1 minute
// used = -1 means idle -> index 0
// used = i means volunteer i works -> index i+1
vector<vector<vector<pair<int,int>>>> adj;

// Encode rest times for volunteers in "positions" into integer v.
// Each rest time is 1..4, stored as (rest-1) in 2 bits.
int encode_state(const vector<int>& rest, const vector<int>& positions) {
    int v = 0;
    for (int j = 0; j < (int)positions.size(); j++) {
        int idx = positions[j];
        v |= (rest[idx] - 1) << (2 * j);
    }
    return v;
}

// Decode integer v into full rest[] (size N). Others not in positions get 0.
void decode_state(int v, const vector<int>& positions, vector<int>& rest) {
    fill(rest.begin(), rest.end(), 0);
    for (int j = 0; j < (int)positions.size(); j++) {
        int idx = positions[j];
        rest[idx] = ((v >> (2 * j)) & 3) + 1; // 0..3 -> 1..4
    }
}

void build_graph() {
    // Enumerate all subsets of size <= 4
    combo_index.assign(1 << N, -1);
    combos.clear();

    for (int mask = 0; mask < (1 << N); mask++) {
        if (__builtin_popcount((unsigned)mask) <= 4) {
            combo_index[mask] = (int)combos.size();
            vector<int> pos;
            for (int i = 0; i < N; i++) if (mask & (1 << i)) pos.push_back(i);
            combos.push_back(pos);
        }
    }

    int C = (int)combos.size();

    // Allocate up to 256 encodings for each combo (max when subset size=4).
    available.assign(C, vector<vector<int>>(256));
    adj.assign(C, vector<vector<pair<int,int>>>(256, vector<pair<int,int>>(N + 1)));

    // Precompute for each (ci, v) the available volunteers and transitions.
    for (int ci = 0; ci < C; ci++) {
        int sz = (int)combos[ci].size();
        int max_v = 1 << (2 * sz); // equals 4^sz, valid encodings are [0..max_v-1]

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

            // Build list of available volunteers
            for (int i = 0; i < N; i++) {
                if (rest[i] == 0 && A[i] > 0) {
                    available[ci][v].push_back(i);
                }
            }

            // Transitions: used = -1 (idle) and used = 0..N-1 (use that volunteer)
            for (int used = -1; used < N; used++) {
                vector<int> new_rest(N, 0);

                // One minute passes:
                // - chosen volunteer becomes resting for B[used]
                // - all others decrement rest by 1
                for (int i = 0; i < N; i++) {
                    if (i == used) new_rest[i] = B[i];
                    else new_rest[i] = max(0, rest[i] - 1);
                }

                // Build new mask of resting volunteers
                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];
                // In the intended solution, reachable states always have <=4 resting people
                // so new_ci must exist.

                int new_v = encode_state(new_rest, combos[new_ci]);
                adj[ci][v][used + 1] = {new_ci, new_v};
            }
        }
    }
}

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

    cin >> M >> N;
    A.resize(N);
    B.resize(N);
    for (int i = 0; i < N; i++) cin >> A[i] >> B[i];

    // Quick impossible check: if all A[i] == 0, we can never inflate any balloon
    bool any = false;
    for (int i = 0; i < N; i++) if (A[i] > 0) any = true;
    if (!any) {
        cout << -1 << "\n";
        return 0;
    }

    build_graph();
    int C = (int)combos.size();

    // dist[bal][ci][v] = minutes, -1 = unvisited
    vector<vector<vector<int>>> dist(M + 1,
        vector<vector<int>>(C, vector<int>(256, -1)));

    queue<tuple<int,int,int>> q;

    // Start: need M balloons, nobody resting => empty subset (mask=0) => some ci, v=0.
    int start_ci = combo_index[0];
    dist[M][start_ci][0] = 0;
    q.push({M, start_ci, 0});

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

        int d = dist[bal][ci][v];
        if (bal == 0) { // earliest reach => minimal time
            cout << d << "\n";
            return 0;
        }

        const auto &avail = available[ci][v];

        if (avail.empty()) {
            // Must idle
            auto [nci, nv] = adj[ci][v][0]; // used=-1
            if (dist[bal][nci][nv] == -1) {
                dist[bal][nci][nv] = d + 1;
                q.push({bal, nci, nv});
            }
        } else {
            // Try using each available volunteer
            for (int i : avail) {
                auto [nci, nv] = adj[ci][v][i + 1]; // used=i
                int nbal = max(0, bal - A[i]);
                if (dist[nbal][nci][nv] == -1) {
                    dist[nbal][nci][nv] = d + 1;
                    q.push({nbal, nci, nv});
                }
            }
        }
    }

    cout << -1 << "\n";
    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()
```

If you want, I can also provide a simplified alternative solution (e.g., binary search on time + max-flow/DP), but the BFS-with-compressed-cooldowns approach above matches the intended constraints and the reference solution style.