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

548. Dragons and Princesses
Time limit per test: 1 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Once upon a time there lived the Knight. Being very courageous he decided to make a long journey full of fights and adventures. The map of this journey can be represented as a row with n cells numbered from 1 to n from left to right. Initially the Knight is located at the leftmost cell (cell number 1). He should pass all the cells one by one and finish his way at the rightmost cell (cell number n). He is not allowed to move back or skip some cells, he will visit all the cells from the first to the last.

Each cell except the first one contains either a dragon or a princess. Each dragon has a chest with gold coins. The dragon at the cell i keeps gi coins. Every time the Knight steps to a cell with a dragon he has a choice  — to kill the dragon or just to pass through. The Knight is very strong and dexterous, so it is not a problem for him to kill any dragon on his way. If a dragon is killed the Knight gets all the gold dragon possessed.

When the Knight steps to the cell with a princess, she wonders how many dragons he has killed. If that number is greater or equal to her beauty bi, the princess considers the Knight brave enough and instantly asks him to marry her. Being a true gentleman, the Knight cannot refuse and his adventure immediately ends.

The Knight loves the princess who lives in the cell number n and wants to marry her. Also during the journey he wants to collect as much gold as possible. Please help him to accomplish this task.

Input
The first line of the input contains a single integer n (2 ≤ n ≤ 2·105) — the number of cells. The next n-1 lines describe cells from 2 to n.

If the cell number i contains a dragon, the i-th line of the input contains letter "d" followed by a single integer gi (1 ≤ gi ≤ 104) — the number of coins the dragon keeps. The letter and the integer are separated by a single space.

If the cell number i contains a princess, the i-th line of the input contains letter "p" followed by a single integer bi (1 ≤ bi ≤ 2·105) — the beauty of the princess. The letter and the integer are separated by a single space. It is guaranteed that the last cell contains a princess.

Output
On the first line of the output print a single integer — the maximum number of gold coins the Knight can collect. On the second line print a single integer k — the number of dragons to kill. The third line should contain k integers — the numbers of the cells where the Knight should kill a dragon. The cell numbers should be printed in the increasing order.

If there are several optimal solutions, output any of them. If the Knight can't marry his beloved princess, just print -1 in the first line of the output.

Example(s)
sample input
sample output
6
d 10
d 12
p 2
d 1
p 2
13
2
3 5

sample input
sample output
6
d 10
d 12
p 2
d 1
p 3
-1

<|response|>
1. Abridged Problem Statement  
You have a linear sequence of n cells, numbered 1 through n. You start at cell 1 and must visit every cell in order without skipping or going backward. Each cell i>1 contains either:  
• A dragon with gᵢ gold coins, which you may choose to kill (gaining its gold) or leave alive.  
• A princess with beauty bᵢ. Upon stepping on her cell, if your total kills so far ≥ bᵢ, she forces you to marry and the journey stops immediately (any remaining cells are unvisited).  

The princess in cell n is the one you love and must marry there. To succeed, when reaching cell n your kill-count must be ≥ bₙ. You want to maximize the gold collected under these constraints. If you cannot reach cell n and marry her, output -1.

2. Key Observations  
• Every intermediate princess i (i<n) enforces the constraint “kill-count before i must be < bᵢ,” or else your journey ends too early.  
• The final princess requires “kill-count ≥ bₙ” to succeed.  
• You’d like to kill as many high-gold dragons as possible, but for each intermediate princess you must keep your kill-count strictly below her beauty.  
• A greedy strategy works: whenever you encounter a dragon, tentatively kill it (add its gold and increment kill-count); whenever you hit a princess with beauty b, if your kill-count has reached b or more, you must “undo” kills until your kill-count is b−1. To lose minimum gold, you always undo your smallest-gold kills.  

3. Full Solution Approach  
Maintain:  
  • A min-heap (priority queue) H storing pairs (gold, cell_index) for all dragons you have chosen to kill.  
  • A running total sum_gold of gold from those kills.  

Process cells in order from 2 to n−1:  
  • If the cell has a dragon with gᵢ:  
      – Push (gᵢ, i) onto H, add gᵢ to sum_gold.  
  • If the cell has a princess with beauty bᵢ:  
      – While H.size() ≥ bᵢ, pop the smallest gold element (g_min, idx_min) from H and subtract g_min from sum_gold.  
        This reduces your kill-count and loses the least gold.  

After processing up to cell n−1, handle the final princess at cell n with beauty bₙ:  
  • If H.size() < bₙ, you cannot meet her requirement → print -1.  
  • Otherwise H represents exactly the set of dragons you kill, and sum_gold is maximized. Output sum_gold, then H.size(), then the sorted list of cell indices in H.  

Time complexity: O(n log n) for heap operations.

4. C++ Implementation with Detailed Comments  
```cpp
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;
    // We'll store the n-1 events (cells 2..n) as pairs (type, value).
    vector<pair<char,int>> events(n-1);
    for (int i = 0; i < n-1; i++) {
        cin >> events[i].first >> events[i].second;
    }

    // Min-heap of (gold, cell_index) for dragons we kill
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> heap;
    long long sum_gold = 0;

    // Process cells 2 through n-1
    for (int i = 0; i < n-2; i++) {
        char type = events[i].first;
        int v    = events[i].second;
        if (type == 'd') {
            // Tentatively kill this dragon
            heap.push({v, i+2});    // store its cell index = i+2
            sum_gold += v;
        } else {
            // Princess with beauty v: we must have kills < v
            // If heap.size() >= v, undo smallest kills
            while ((int)heap.size() >= v) {
                auto top = heap.top();
                heap.pop();
                sum_gold -= top.first;
            }
        }
    }

    // Now handle the final princess at cell n
    char last_type = events.back().first;
    int last_beauty = events.back().second;
    if (last_type != 'p' || (int)heap.size() < last_beauty) {
        // Cannot marry the final princess
        cout << -1 << "\n";
        return 0;
    }

    // Otherwise, output maximum gold and which dragons we killed
    cout << sum_gold << "\n";
    cout << heap.size() << "\n";
    // Extract and sort the cell indices
    vector<int> answer;
    answer.reserve(heap.size());
    while (!heap.empty()) {
        answer.push_back(heap.top().second);
        heap.pop();
    }
    sort(answer.begin(), answer.end());
    for (int idx : answer) {
        cout << idx << " ";
    }
    cout << "\n";
    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys
import heapq

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

    # Min-heap of (gold, cell_index)
    heap = []
    sum_gold = 0

    # Process cells 2..n-1
    for i in range(n-2):
        typ, val = events[i]
        if typ == 'd':
            # Kill dragon tentatively
            heapq.heappush(heap, (val, i+2))
            sum_gold += val
        else:
            # Princess with beauty val: must have kills < val
            # If too many kills, remove smallest-gold ones
            while len(heap) >= val:
                smallest_gold, _ = heapq.heappop(heap)
                sum_gold -= smallest_gold

    # Final princess at cell n
    last_typ, last_beauty = events[-1]
    if last_typ != 'p' or len(heap) < last_beauty:
        # Can't marry beloved princess
        print(-1)
        return

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

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