## 1) Abridged problem statement

There are **K** party rounds and **N** tea types. Each tea type `i` has a **cost per bag** `c[i]` and a **kind** `s[i]` (`0` = green, `1` = black).

- In round 1 there are `K` guests; after each round **one guest leaves**, so round `t` uses `(K - t + 1)` bags.
- In each round you choose **one tea type**, and all bags that round are that type.
- Constraints:
  1. All chosen tea types across the `K` rounds must be **distinct**.
  2. In any **three consecutive rounds**, teas cannot all be of the **same kind** (i.e., you may not have `GGG` or `BBB` as a substring).

Goal: **minimize total cost** of all bags used. Output any optimal sequence of `K` distinct tea indices, or `"Impossible"`.

---

## 2) Detailed editorial (solution explanation)

### Key cost structure
If a tea with cost `c` is used at a round where `g` guests are present, it contributes `g * c` to total cost. Guest counts are:
`K, K-1, ..., 1`.

So earlier rounds are "more expensive" to assign costly teas to.

### Observation 1: within a fixed kind, use teas in increasing cost order
Suppose we decide the **kinds pattern** across rounds (e.g., `G B G ...`). Then the only freedom is: *which green tea is used for each G-position* and similarly for black.

Within the green positions, if a more expensive green tea is assigned to an earlier (higher guest count) green slot than a cheaper green tea, swapping them strictly decreases cost (rearrangement inequality / inversion swap). Same for black.

Therefore:
- If we use `cg` green teas total, the optimal choice is the **cheapest `cg` green teas**, used in increasing cost order in the green slots.
- If we use `cb` black teas total, the optimal choice is the **cheapest `cb` black teas**, used in increasing cost order in the black slots.

This reduces the problem to choosing:
1. how many green/black teas we take, and
2. the interleaving pattern of kinds, under the "no 3 consecutive same kind" constraint.

### Observation 2: prefix property
Because we always take the cheapest teas of each kind, we never need to "skip" a cheaper tea and take a more expensive one of the same kind. Thus the selected set is a **prefix** of the sorted list for each kind.

So the only state needed is: how many green/black we have already taken.

### Dynamic programming state
Split teas into two arrays:

- `green_teas = [(cost, original_index), ...]` sorted by cost
- `black_teas = [(cost, original_index), ...]` sorted by cost

Let:
- `cg` = number of green teas chosen so far
- `cb` = number of black teas chosen so far
- `pos = cg + cb` = number of rounds already planned (0..K)

We must ensure we never create 3 consecutive rounds of the same kind. For that, keep a small "tail" state describing the last 1–2 kinds:

Use 5 states:
- `0` = start (no previous)
- `1` = last is `G`
- `2` = last is `B`
- `3` = last two are `GG`
- `4` = last two are `BB`

Transitions when choosing next kind:
- From `...G` (state 1), choosing `G` → `...GG` (state 3); choosing `B` → `...B` (state 2)
- From `...B` (state 2), choosing `B` → `...BB` (state 4); choosing `G` → `...G` (state 1)
- From `...GG` (state 3), cannot choose `G`; choosing `B` → state 2
- From `...BB` (state 4), cannot choose `B`; choosing `G` → state 1
- From `start` (0), choosing `G` → 1, choosing `B` → 2

DP definition:
`dp[cb][cg][state] = minimal total cost after selecting cb black and cg green teas, ending in tail=state`

Initialization:
`dp[0][0][0] = 0`

Transition:
We are about to schedule round `pos+1`, with `guests = K - pos`.

If we choose next tea as green:
- requires `cg < number_of_green` and `cg < K`
- new cost = `dp + guests * green_teas[cg].cost` (because `cg` already chosen; next is index `cg`)
- new state from transition table
- new counts: `cg+1`

Similarly for black.

Complexities:
- `cb` ranges up to `min(nb, K)`, `cg` up to `min(ng, K)`.
- Total states `O(K^2 * 5)`; transitions constant.
- Fits easily.

### Reconstructing the answer
Store parent pointers:
`par[ncb][ncg][ns] = (cb, cg, s)` when we improve a state.

At the end, among states with `cb+cg = K`, choose minimal dp.

Backtrack from best `(cb, cg, s)` down to `(0,0,0)`:
- If `cg` decreased, the last chosen was green: output `green_teas[cg-1].original_index`
- else it was black: output `black_teas[cb-1].original_index`

If all dp at length K are INF, print `"Impossible"`.

---

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

void read() {
    cin >> k >> n;
    tea.resize(n);
    cin >> tea;
}

void solve() {
    // The first observation is that in an optimal arrangement for a given type
    // of tea, is always going to be in increasing order of price - if this
    // wasn't the case, we can swap any inversion to achieve a better
    // configuration. If we didn't have the three consecutive rounds constraint,
    // the optimal order would have been true for all selected teas, but we
    // have cases like N=5, K=5 and (1, b), (2, b), (0, g), (3, b), (4, b): here
    // this is the only valid option and the (0, g) is out of order. However,
    // we can show that it's always optimal to keep a prefix of the black and
    // green teas when sorted - if we get some tea i we should also get all teas
    // before i of the same colour. This gives us a direct DP solution with
    // state dp[cnt_black][cnt_green][tail_state]. At each position we can
    // either take the next black, or the next green tea (with index
    // cnt_{black,green}+1). This works in O(K^2). In terms of implementation,
    // the tail states we use are: 0=start, 1=...G, 2=...B, 3=...GG, 4=...BB.

    vector<pair<int, int>> black_teas, green_teas;
    for(int i = 0; i < n; i++) {
        auto [cost, kind] = tea[i];
        if(kind == 1) {
            black_teas.emplace_back(cost, i + 1);
        } else {
            green_teas.emplace_back(cost, i + 1);
        }
    }
    ranges::sort(black_teas);
    ranges::sort(green_teas);

    int nb = (int)black_teas.size();
    int ng = (int)green_teas.size();

    constexpr int NUM_STATES = 5;
    constexpr int transition[NUM_STATES][2] = {
        {1, 2}, {3, 2}, {1, 4}, {-1, 2}, {1, -1},
    };

    auto fill_val = array<int64_t, 5>{};
    ranges::fill(fill_val, numeric_limits<int64_t>::max());
    vector dp(min(nb, k) + 1, vector(min(ng, k) + 1, fill_val));

    struct Parent {
        int cb, cg, state;
    };
    vector par(min(nb, k) + 1, vector(min(ng, k) + 1, array<Parent, 5>{{}}));

    dp[0][0][0] = 0;

    for(int cb = 0; cb <= min(nb, k); cb++) {
        for(int cg = 0; cg <= min(ng, k); cg++) {
            int pos = cb + cg;
            if(pos >= k) {
                continue;
            }
            int guests = k - pos;

            for(int s = 0; s < NUM_STATES; s++) {
                if(dp[cb][cg][s] == numeric_limits<int64_t>::max()) {
                    continue;
                }

                for(int choice: {0, 1}) {
                    int ns = transition[s][choice];
                    if(ns == -1) {
                        continue;
                    }

                    auto& teas = choice == 0 ? green_teas : black_teas;
                    int cnt = choice == 0 ? cg : cb;
                    int max_cnt = choice == 0 ? ng : nb;
                    if(cnt >= max_cnt || cnt >= k) {
                        continue;
                    }

                    int64_t new_cost =
                        dp[cb][cg][s] + (int64_t)guests * teas[cnt].first;
                    int ncb = cb + choice, ncg = cg + (1 - choice);

                    if(new_cost < dp[ncb][ncg][ns]) {
                        dp[ncb][ncg][ns] = new_cost;
                        par[ncb][ncg][ns] = {cb, cg, s};
                    }
                }
            }
        }
    }

    int64_t best = numeric_limits<int64_t>::max();
    int best_cb = -1, best_cg = -1, best_state = -1;
    for(int cb = 0; cb <= min(nb, k); cb++) {
        int cg = k - cb;
        if(cg < 0 || cg > ng) {
            continue;
        }
        for(int s = 0; s < NUM_STATES; s++) {
            if(dp[cb][cg][s] < best) {
                best = dp[cb][cg][s];
                best_cb = cb;
                best_cg = cg;
                best_state = s;
            }
        }
    }

    if(best == numeric_limits<int64_t>::max()) {
        cout << "Impossible" << '\n';
        return;
    }

    vector<int> result(k);
    int cb = best_cb, cg = best_cg, s = best_state;
    for(int pos = k - 1; pos >= 0; pos--) {
        auto [pcb, pcg, ps] = par[cb][cg][s];
        if(pcg < cg) {
            result[pos] = green_teas[cg - 1].second;
        } else {
            result[pos] = black_teas[cb - 1].second;
        }
        cb = pcb;
        cg = pcg;
        s = ps;
    }

    cout << result << '\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 (same approach) with detailed comments

```python
import sys

INF = 10**30

def solve() -> None:
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    K = int(next(it))
    N = int(next(it))

    green = []  # list of (cost, original_index)
    black = []  # list of (cost, original_index)

    for i in range(1, N + 1):
        c = int(next(it))
        s = int(next(it))
        if s == 0:
            green.append((c, i))
        else:
            black.append((c, i))

    # Sort by increasing cost so that taking a prefix is optimal
    green.sort()
    black.sort()

    ng = len(green)
    nb = len(black)

    # Tail states:
    # 0=start, 1=...G, 2=...B, 3=...GG, 4=...BB
    transition = [
        [1, 2],   # start
        [3, 2],   # ...G
        [1, 4],   # ...B
        [-1, 2],  # ...GG
        [1, -1],  # ...BB
    ]
    NUM_STATES = 5

    max_b = min(nb, K)
    max_g = min(ng, K)

    # dp[cb][cg][s] = min cost, initialize to INF
    dp = [[[INF] * NUM_STATES for _ in range(max_g + 1)] for __ in range(max_b + 1)]

    # parent pointers to reconstruct:
    # par[cb][cg][s] = (prev_cb, prev_cg, prev_state)
    par = [[[(0, 0, 0)] * NUM_STATES for _ in range(max_g + 1)] for __ in range(max_b + 1)]

    dp[0][0][0] = 0

    for cb in range(max_b + 1):
        for cg in range(max_g + 1):
            pos = cb + cg
            if pos >= K:
                continue
            guests = K - pos  # guests in next round

            for s in range(NUM_STATES):
                cur = dp[cb][cg][s]
                if cur >= INF:
                    continue

                # choice=0 -> green, choice=1 -> black
                for choice in (0, 1):
                    ns = transition[s][choice]
                    if ns == -1:
                        continue

                    if choice == 0:
                        cnt = cg
                        if cnt >= ng or cnt >= K or cg >= max_g:
                            continue
                        cost = green[cnt][0]
                        ncb, ncg = cb, cg + 1
                    else:
                        cnt = cb
                        if cnt >= nb or cnt >= K or cb >= max_b:
                            continue
                        cost = black[cnt][0]
                        ncb, ncg = cb + 1, cg

                    new_cost = cur + guests * cost
                    if new_cost < dp[ncb][ncg][ns]:
                        dp[ncb][ncg][ns] = new_cost
                        par[ncb][ncg][ns] = (cb, cg, s)

    # pick best end with cb+cg=K
    best = INF
    best_cb = best_cg = best_s = -1

    for cb in range(max_b + 1):
        cg = K - cb
        if cg < 0 or cg > max_g:
            continue
        for s in range(NUM_STATES):
            if dp[cb][cg][s] < best:
                best = dp[cb][cg][s]
                best_cb, best_cg, best_s = cb, cg, s

    if best >= INF:
        sys.stdout.write("Impossible\n")
        return

    # reconstruct chosen tea indices in order
    ans = [0] * K
    cb, cg, s = best_cb, best_cg, best_s

    for pos in range(K - 1, -1, -1):
        pcb, pcg, ps = par[cb][cg][s]

        # If green count decreased, last pick was green; else black
        if pcg < cg:
            ans[pos] = green[cg - 1][1]
        else:
            ans[pos] = black[cb - 1][1]

        cb, cg, s = pcb, pcg, ps

    sys.stdout.write(" ".join(map(str, ans)) + "\n")


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

---

## 5) Compressed editorial

- Sort green teas by cost and black teas by cost.
- In an optimal plan, for each kind you take the **cheapest prefix** and use them in increasing-cost order in that kind's rounds (swap argument).
- DP over counts `(cb, cg)` and last-two-kinds tail state to enforce "no 3 consecutive same kind".
  - States: start, G, B, GG, BB (5 states).
  - Transition by choosing next kind (green/black) if it doesn't create `GGG`/`BBB`.
  - Add cost: `(K - (cb+cg)) * cost_of_next_cheapest_of_that_kind`.
- Choose best DP state with `cb+cg = K`; backtrack with parent pointers to output original indices.
- If unreachable, print `"Impossible"`.
