## 1. Abridged problem statement

There are `N` contest problems and `T` minutes of training time. Problem `i` takes exactly `t[i]` minutes to solve.

There are `M` prerequisite constraints `(a, b)`, meaning problem `a` must be solved before problem `b`. It is guaranteed that `t[a] <= t[b]`.

If the team solves problems at completion times `c1, c2, ...`, the penalty is `c1 + c2 + ...`.

Find:

1. The maximum number of problems the team can solve within `T` minutes.
2. Among schedules solving that many problems, the minimum possible penalty.
3. One valid order of problems achieving this.

If constraints contain cycles, problems in those cycles cannot be solved.

---

## 2. Detailed editorial

### Key observations

For a fixed set of solved problems, the penalty is minimized by solving shorter problems earlier.

For example, suppose two independent problems take `x` and `y` minutes, with `x <= y`.

Solving `x` then `y` gives contribution:

```text
x + (x + y) = 2x + y
```

Solving `y` then `x` gives:

```text
y + (y + x) = x + 2y
```

Since `x <= y`, the first order is no worse.

So, without prerequisites, the optimal strategy is simply to solve problems in increasing order of `t[i]`.

The only complication is prerequisites.

However, the input guarantees that for every constraint `a -> b`:

```text
t[a] <= t[b]
```

That means prerequisite edges never force a longer problem before a shorter one. Therefore, sorting by increasing solving time is compatible with prerequisites, except possibly among problems with equal solving time. Equal-time problems can be ordered according to the directed constraints.

So we need a topological order that always chooses the currently available problem with the smallest solving time.

---

### Handling prerequisites

Use Kahn's algorithm for topological sorting.

Normally, Kahn's algorithm keeps a queue of nodes whose indegree is zero.

Here, instead of a queue, use a min-heap ordered by:

```text
(t[i], i)
```

At each step:

1. Take the available problem with minimum solving time.
2. If solving it would exceed total training time, stop.
3. Otherwise, solve it.
4. Remove its outgoing edges.
5. Any newly available problems are pushed into the heap.

---

### Why this is optimal

The heap-based Kahn algorithm gives a valid prerequisite order.

Also, because every edge goes from a problem of smaller or equal time to a problem of larger or equal time, the produced order is non-decreasing by solving time.

Indeed, when a problem `u` is popped, any newly unlocked problem `v` satisfies:

```text
t[u] <= t[v]
```

So the algorithm can never introduce a newly available problem that is shorter than one already popped.

Therefore, the produced order is essentially the globally shortest-first feasible order.

Now consider the prefix of this order.

If the first `k` problems fit in time, then they form a valid solution solving `k` problems.

If the first `k + 1` problems do not fit, then no other set of `k + 1` solvable problems can fit either, because the first `k + 1` problems are the shortest feasible `k + 1` problems.

So the longest prefix that fits maximizes the number of solved problems.

Since the prefix is in non-decreasing solving time order, it also minimizes the penalty among schedules solving that many problems.

---

### Cycles

If there is a directed cycle, none of the problems in that cycle can be solved, because each requires another one to be solved earlier.

Kahn's algorithm naturally handles this: nodes in cycles never reach indegree zero, so they are never pushed into the heap.

---

### Complexity

Let `N` be the number of problems and `M` the number of constraints.

Each problem enters and leaves the heap at most once.

Each edge is processed once.

Therefore:

```text
Time complexity:  O((N + M) log N)
Memory complexity: O(N + M)
```

This easily fits the constraints.

---

## 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;
int64_t total_time;
vector<int> t;
vector<vector<int>> adj;
vector<int> indeg;

void read() {
    cin >> n >> total_time;
    t.assign(n + 1, 0);
    for(int i = 1; i <= n; i++) {
        cin >> t[i];
    }

    adj.assign(n + 1, {});
    indeg.assign(n + 1, 0);
    int m;
    cin >> m;
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        indeg[b]++;
    }
}

void solve() {
    // The penalty is the sum of completion times, so for a fixed set of solved
    // problems the penalty is minimized by solving them in non-decreasing order
    // of solving time (shortest first weights the cheap problems into the most
    // prefixes). The set we actually solve must also be closed under the
    // prerequisite relation: to solve b we must first solve every ancestor a.
    //
    // The crucial guarantee is that every constraint a -> b has ta <= tb, which
    // means the prerequisite order never contradicts the "easy problems first"
    // order. Sorting by solving time therefore already respects all
    // constraints, except between equally hard problems where an explicit
    // a -> b with ta = tb forces a before b. So we run Kahn's topological sort
    // but instead of an arbitrary queue we keep a min-heap of the currently
    // available problems keyed by solving time, always emitting the cheapest
    // one. This yields a single order that is simultaneously a valid
    // topological order and globally non-decreasing in solving time.
    //
    // Because the order is non-decreasing in time, each prefix is the cheapest
    // prerequisite-closed set of its size, so we just walk the order
    // accumulating time and stop the moment the next (and hence every
    // remaining) problem no longer fits in the training duration. That prefix
    // maximizes the count and, being increasing in time, also minimizes the
    // penalty. Problems trapped in a cycle never reach in-degree zero, so they
    // are naturally never emitted, which matches the fact that a cycle of
    // mutual prerequisites is unsolvable.

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    for(int i = 1; i <= n; i++) {
        if(indeg[i] == 0) {
            pq.push({t[i], i});
        }
    }

    vector<int> order;
    int64_t elapsed = 0, penalty = 0;
    while(!pq.empty()) {
        auto [ti, u] = pq.top();
        pq.pop();
        if(elapsed + ti > total_time) {
            break;
        }

        elapsed += ti;
        penalty += elapsed;
        order.push_back(u);
        for(int v: adj[u]) {
            if(--indeg[v] == 0) {
                pq.push({t[v], v});
            }
        }
    }

    cout << order.size() << ' ' << penalty << '\n';
    cout << order << '\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 with detailed comments

```python
import sys
import heapq


def solve():
    # Read all input tokens.
    data = sys.stdin.read().strip().split()

    # If input is empty, do nothing.
    if not data:
        return

    # Pointer into the token list.
    ptr = 0

    # Read number of problems and total training time.
    n = int(data[ptr])
    ptr += 1

    total_time = int(data[ptr])
    ptr += 1

    # Use 1-based indexing.
    # t[0] is unused.
    t = [0] * (n + 1)

    # Read solving times.
    for i in range(1, n + 1):
        t[i] = int(data[ptr])
        ptr += 1

    # Read number of prerequisite constraints.
    m = int(data[ptr])
    ptr += 1

    # adj[u] contains all problems v such that u must be solved before v.
    adj = [[] for _ in range(n + 1)]

    # indeg[v] is the number of remaining prerequisites of v.
    indeg = [0] * (n + 1)

    # Read all constraints.
    for _ in range(m):
        a = int(data[ptr])
        ptr += 1

        b = int(data[ptr])
        ptr += 1

        # Edge a -> b.
        adj[a].append(b)

        # b has one more prerequisite.
        indeg[b] += 1

    # Min-heap of currently available problems.
    # Each element is (solving_time, problem_index).
    heap = []

    # Initially, problems with zero indegree have no prerequisites.
    for i in range(1, n + 1):
        if indeg[i] == 0:
            heapq.heappush(heap, (t[i], i))

    # Chosen solving order.
    order = []

    # Total time already spent.
    elapsed = 0

    # Total penalty.
    penalty = 0

    # Kahn's algorithm with a min-heap.
    while heap:
        # Get available problem with smallest solving time.
        ti, u = heapq.heappop(heap)

        # If even the shortest available problem does not fit,
        # then no remaining feasible problem can improve the answer.
        if elapsed + ti > total_time:
            break

        # Solve problem u.
        elapsed += ti

        # Add its completion time to the penalty.
        penalty += elapsed

        # Store it in the answer.
        order.append(u)

        # Remove outgoing edges u -> v.
        for v in adj[u]:
            # One prerequisite of v has been solved.
            indeg[v] -= 1

            # If all prerequisites of v are solved, it becomes available.
            if indeg[v] == 0:
                heapq.heappush(heap, (t[v], v))

    # Prepare output.
    out = []

    # First line: number of solved problems and minimal penalty.
    out.append(f"{len(order)} {penalty}")

    # Second line: order of solved problems.
    # If order is empty, this becomes an empty line.
    out.append(" ".join(map(str, order)))

    # Print result.
    sys.stdout.write("\n".join(out))


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

---

## 5. Compressed editorial

Use Kahn's topological sort, but store available zero-indegree problems in a min-heap by solving time.

Because every constraint `a -> b` satisfies `t[a] <= t[b]`, prerequisites never require solving a longer problem before a shorter one. Thus, repeatedly choosing the shortest currently available problem produces a valid topological order whose solving times are non-decreasing.

Walk through this order, accumulating elapsed time and penalty. Stop when the next problem would exceed `T`.

The chosen prefix is optimal:

- It is prerequisite-valid.
- It contains the maximum possible number of problems, because no other set of the same larger size can have smaller total solving time.
- Its penalty is minimal because problems are solved in shortest-first order.

Cycles are automatically ignored by Kahn's algorithm, since their nodes never reach indegree zero.

Complexity:

```text
O((N + M) log N)
```
