<|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.

304. Mars Stomatology
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Martian girl Kate has a toothache. The martian anatomy is very specific. They all have N teeth, each situated on one of K gums. Kate should pay dentist Ai mars euros for the treatment of i-th tooth. Moreover, Kate should pay Bj euros for the anesthesia of the gum j if this gum has at least one tooth cured. What is the maximal number of teeth Kate can cure if parents gave her P mars euros?

Input
The first line of the input contains three integer numbers N, K and P (1≤ N≤ 600; 1≤ K≤ N; 1≤ P≤ 106). The second line contains the sequence of K integer numbers B1, B2,..., BK, where Bj is the cost of anesthesia of the j-th gum (1≤ Bj≤ 600 for all j = 1, 2,..., K). Each of the following N lines contains the description of tooth. Each description is the pair of integer numbers Ai and Ci, where Ai is the cost of curing of the i-th tooth, Ci is the number of the gum the tooth occupies (1≤ Ai≤ 600; 1≤ Ci≤ K for all i = 1, 2,..., N).

Output
Write to the first line of the output the maximal number of cured teeth S. Write to the second line S numbers of the cured teeth from the given set. If there are several solutions output any of them.

Example(s)
sample input
sample output
4 2 10
1 2
1 2
5 2
3 1
3 2
3
4 3 1

<|response|>
## 1. Abridged Problem Statement

Kate has N teeth distributed over K gums. Treating the i-th tooth costs Aᵢ, and if she treats ≥1 tooth on gum j she must pay a fixed anesthesia cost Bⱼ. Given a total budget P, choose a subset of teeth to maximize the number of treated teeth. Output that maximum count and any valid list of tooth indices.

---

## 2. Detailed Editorial

### Problem Reformulation

- You have K groups (gums).
- In group j there are nⱼ teeth, each with treatment cost aᵢ.
- If you take at least one item from group j you pay a group-fixed cost Bⱼ once.
- You have a total budget P. Maximize the total items selected.

This is a "grouped knapsack" where each group carries:
- A fixed setup cost Bⱼ if you pick ≥1 from that group.
- Individual costs aᵢ for each picked item in the group.
- We want to maximize total picked items under budget P.

### DP State

Let `dp[g][t]` = minimal total cost to select exactly t teeth from the first g gums.
We maintain `dp` as an array of size (K+1)×(N+1), initialized to ∞ except `dp[0][0] = 0`.

### Transitions

For gum index g from 0 to K−1, consider two options for each achievable t:
1. Take zero teeth from gum g+1:
   `dp[g+1][t] = min(dp[g+1][t], dp[g][t])`
2. Take p ≥1 teeth (up to min(n_g, N−t)) from this gum:
   - First sort that gum's teeth by ascending aᵢ.
   - Precompute prefix sums of those sorted costs.
   - The incremental cost of taking p teeth is B[g] + prefix_sum[p].
   - Update `dp[g+1][t+p] = min(dp[g+1][t+p], dp[g][t] + incremental_cost)`.

After filling all K groups, scan t from 0…N to find the maximum t such that `dp[K][t] ≤ P`. That t is your answer.

### Reconstruction

To reconstruct which teeth were taken:
- Store for each `dp[g+1][…]` the value p of how many teeth you picked from gum g (or -1 if 0).
- Starting from (g=K, t=best_t), step g→g−1, read p = choice[g][t], if p>0 add the first p sorted tooth indices of gum g to the solution list, and set t := t−p.

### Complexity

- Sorting each gum's teeth: total O(N log N).
- DP has K stages, each stage loops t=0..N and p up to n_g. So overall O(∑g N·n_g) = O(N²). With N≤600 this is ~360K operations, easily within time.

---

## 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 n, k, p;
vector<int> b;
vector<vector<pair<int, int>>> gums;

void read() {
    cin >> n >> k >> p;
    b.resize(k);
    cin >> b;
    gums = vector<vector<pair<int, int>>>(k);
    for(int i = 0; i < n; ++i) {
        int cost, gum;
        cin >> cost >> gum;
        gums[gum - 1].push_back({cost, i + 1});
    }

    for(auto& gum: gums) {
        sort(gum.begin(), gum.end());
    }
}

void solve() {
    // To cure t teeth as cheaply as possible we choose, per gum, how many of its
    // teeth to treat; within a gum it is always optimal to take the cheapest
    // ones, so each gum's teeth are pre-sorted by cost. Curing any teeth on a
    // gum also pays its anesthesia b[g].
    //
    // dp[g][t] = minimum total cost to cure exactly t teeth using only the first
    // g gums, stored as {cost, count taken from gum g}. Transitions from
    // dp[g][t] either skip gum g (count -1) or take its p + 1 cheapest teeth,
    // paying b[g] plus their prefix-sum of costs.
    //
    // The answer is the largest t whose minimum cost is at most p; we then walk
    // the stored counts back from dp[k][t] to recover which teeth were chosen.

    vector<vector<pair<int, int>>> dp(
        k + 1, vector<pair<int, int>>(n + 1, {INT_MAX, 0})
    );
    dp[0][0] = {0, 0};

    for(int g = 0; g < k; ++g) {
        for(int t = 0; t <= n; ++t) {
            if(dp[g][t].first == INT_MAX) {
                continue;
            }

            int cost = b[g];
            if(dp[g][t].first < dp[g + 1][t].first) {
                dp[g + 1][t] = {dp[g][t].first, -1};
            }

            for(int j = 0; j < min((int)gums[g].size(), n - t); ++j) {
                cost += gums[g][j].first;
                if(dp[g][t].first + cost < dp[g + 1][t + j + 1].first) {
                    dp[g + 1][t + j + 1] = {dp[g][t].first + cost, j + 1};
                }
            }
        }
    }

    int max_teeth = 0;
    while(max_teeth < n && dp[k][max_teeth + 1].first <= p) {
        max_teeth++;
    }

    cout << max_teeth << '\n';

    vector<int> solution;
    int current_teeth = max_teeth;
    for(int g = k; g > 0; --g) {
        int selected = dp[g][current_teeth].second;
        if(selected != -1) {
            for(int i = 0; i < selected; ++i) {
                solution.push_back(gums[g - 1][i].second);
            }

            current_teeth -= selected;
        }
    }

    sort(solution.begin(), solution.end());
    cout << solution << '\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();
        solve();
    }

    return 0;
}
```

---

## 4. Python Solution

```python
import sys
input = sys.stdin.readline

def main():
    N, K, P = map(int, input().split())
    B = list(map(int, input().split()))  # anesthesia costs
    gums = [[] for _ in range(K)]        # list of lists for each gum

    # Read each tooth and append to its gum: (cost, index)
    for idx in range(1, N+1):
        a, c = map(int, input().split())
        gums[c-1].append((a, idx))

    # Sort each gum by ascending tooth cost
    for g in range(K):
        gums[g].sort()

    INF = 10**18
    # dp[g][t] = minimal cost to treat t teeth using first g gums
    # choice[g][t] = how many we took from gum g-1 (or -1 if zero)
    dp = [[INF]*(N+1) for _ in range(K+1)]
    choice = [[0]*(N+1) for _ in range(K+1)]
    dp[0][0] = 0

    # DP transitions
    for g in range(K):
        for t in range(N+1):
            if dp[g][t] == INF:
                continue
            base = dp[g][t]
            # Option 1: take 0
            if base < dp[g+1][t]:
                dp[g+1][t] = base
                choice[g+1][t] = -1
            # Option 2: take p >= 1
            cost_acc = B[g]
            max_p = min(len(gums[g]), N - t)
            for p in range(max_p):
                cost_acc += gums[g][p][0]   # add p-th cheapest tooth cost
                nt = t + p + 1
                nc = base + cost_acc
                if nc < dp[g+1][nt]:
                    dp[g+1][nt] = nc
                    choice[g+1][nt] = p + 1

    # Find the max teeth count within P
    best = 0
    for t in range(N+1):
        if dp[K][t] <= P:
            best = t
    print(best)

    # Reconstruct solution
    res = []
    t = best
    for g in range(K, 0, -1):
        took = choice[g][t]
        if took > 0:
            # collect the first 'took' indices from gums[g-1]
            for i in range(took):
                res.append(gums[g-1][i][1])
            t -= took

    res.sort()
    print(*res)

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

---

## 5. Compressed Editorial

- Group teeth by gum, sort each group's costs.
- Use `dp[g][t]` = minimal cost to pick t teeth from first g gums.
- Transition by either skipping a gum or paying B[g]+prefix_sum of p smallest in that gum.
- Scan `dp[K][t]` for largest t ≤ P. Reconstruct via stored pick counts.
