1. Abridged Problem Statement
You traverse cells 1→n. Each cell i>1 has either a dragon (d, with gₖ gold) or a princess (p, with beauty bₖ). When you step on a dragon you may kill it to gain its gold. When you step on a princess and have already killed ≥bₖ dragons, she forces you to marry and the journey ends immediately. The last cell (n) is your beloved princess—you must arrive there with kills ≥bₙ to succeed. Otherwise (or if any earlier princess stops you) you fail. Choose which dragons to kill so as to maximize total gold, or report –1 if you cannot reach the last princess with enough kills.

2. Detailed Editorial
We need to select a subset of dragons to kill, subject to:
- For every princess at position i<n with beauty bᵢ, the number of kills before i must be <bᵢ, otherwise the journey ends too early.
- At the final princess (position n), kills must be ≥bₙ to succeed.

We want to maximize the sum of gold on killed dragons.

Key insight: You'd like to kill as many high-gold dragons as possible, but certain princesses cap the total number you can have killed so far. Use a greedy "kill-every-dragon, but if you exceed some princess's limit, un-kill your worst kill" strategy. Concretely:

Maintain:
- A min-heap H of pairs (gold, 0-based index) of dragons you have chosen to kill so far.
- A running sum `sum` of those gold amounts.

Process the cells from 2 to n−1:
- If it's a dragon with g gold:
  Push (g, index) onto H, add g to `sum`.
- If it's a princess with beauty b:
  While H.size() ≥ b, pop the smallest gold element x from H and subtract x from `sum`.
  This ensures we keep at most b−1 kills before her, minimizing gold loss.

After processing cell n−1, handle the last cell (princess with beauty bₙ):
- If H.size() < bₙ, output −1 (not enough kills to marry).
- Otherwise, `sum` is already maximal under all earlier constraints, and H contains exactly the set of dragons we kill. Output `sum`, then H.size(), then the sorted list of cell indices corresponding to elements in H.

Time complexity is O(n log n).

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;
vector<pair<char, int>> a;

void read() {
    cin >> n;
    a.resize(n - 1);
    for(int i = 0; i < n - 1; i++) {
        cin >> a[i].first >> a[i].second;
    }
}

void solve() {
    // Walk left to right, greedily keeping every dragon killed so far in a
    // min-heap keyed by the gold it holds (sum tracks the total gold of the
    // currently kept dragons). When we reach a princess with beauty x, the
    // Knight may not have killed x or more dragons or she would marry him and
    // end the journey early; so while the heap holds at least x dragons we
    // discard the cheapest ones until fewer than x remain.
    //
    // The final cell is the beloved princess: the chosen set is valid iff
    // after processing all earlier cells the heap holds fewer dragons than her
    // beauty. The remaining dragons in the heap are exactly the ones to kill,
    // and their stored 1-based cell indices form the answer.

    int sum = 0;
    priority_queue<
        pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>
        q;

    for(int i = 0; i < n - 2; i++) {
        auto [c, x] = a[i];
        if(c == 'd') {
            sum += x;
            q.push({x, i});
        } else {
            while((int)q.size() >= x) {
                sum -= q.top().first;
                q.pop();
            }
        }
    }

    if(a.back().first != 'p' || (int)q.size() < a.back().second) {
        cout << -1 << '\n';
        return;
    }

    cout << sum << '\n';
    vector<int> kills;
    while(!q.empty()) {
        kills.push_back(q.top().second + 2);
        q.pop();
    }

    cout << kills.size() << '\n';
    sort(kills.begin(), kills.end());
    cout << kills << '\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
------------------

```python
import sys
import heapq

def main():
    data = sys.stdin.read().split()
    # Read n and then n-1 lines of (type, value)
    it = iter(data)
    n = int(next(it))
    events = [(next(it), int(next(it))) for _ in range(n-1)]

    # min-heap of (gold, index) for dragons we choose to kill
    heap = []
    sum_gold = 0

    # Process events[0..n-2) i.e. cells 2..n-1
    for i in range(n-2):
        typ, v = events[i]
        if typ == 'd':
            # Tentatively kill dragon: push to heap
            sum_gold += v
            heapq.heappush(heap, (v, i+2))  # store cell index = i+2
        else:
            # At a princess with beauty v: enforce kills < v
            # If we have too many kills, remove the smallest-gold ones
            while len(heap) >= v:
                small_gold, _ = heapq.heappop(heap)
                sum_gold -= small_gold

    # Handle last princess
    last_typ, last_b = events[-1]
    if last_typ != 'p' or len(heap) < last_b:
        # Cannot marry beloved princess
        print(-1)
        return

    # Otherwise, output the results
    print(sum_gold)
    # Extract and sort killed dragon cell indices
    killed = [idx for (_, idx) in heap]
    killed.sort()
    print(len(killed))
    print(*killed)

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

5. Compressed Editorial
Greedy: always "kill" every dragon into a min-heap, accumulating gold; at each intermediate princess with beauty b, if heap size ≥b, repeatedly pop the smallest-gold kills to keep kills <b. At the final princess check heap size ≥bₙ; if so your current sum is maximal, else output –1. This runs in O(n log n).
