p367.in2
======================
3 10
1 1 1
3
1 2
2 3
3 1

=================
p367.in3
======================
4 2
1 2 1 2
1
1 3

=================
p367.ans1
======================
1 1
1

=================
p367.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;
}

=================
statement.txt
======================
367. Contest
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



In compliance with the traditional rules of ACM International Collegiate Programming Contest teams are ranked according to the amount solved problems and penalty time. For the purpose of this problem we will define penalty time as a sum of minutes when all problems solved by the team were submitted (thus, let's think that all problems were accepted from the first attempt). For example, if some team solved three problems: on 10-th, 45-th and 123-rd minutes, the penalty time would be 10 + 45 + 123 = 178 minutes.

On one of numerous trainings one famous team was solving old competition it had solved previously. For each problem participants estimated time ti required to solve this problem. Moreover, they defined a set of constraints on problem solving. Each constraint is an ordered pair (a, b), denoting that the problem a must be solved before the problem b (i. e. if the problem b will be solved, than the problem a also must be solved, and must be solved earlier than the problem b). This is due to the fact that the problem a is a subtask of the problem b. Obviously the problem a is easier than the problem b, i. e. ta ≤ tb. The training lasts T minutes.

What is the best performance can show the team? You may assume that the team will not do failed attempts and that they estimated time for solving each problem correctly. Calculate maximal number of problems that they can solve and the corresponding minimal penalty time. Please also determine which problems and in what order the team should solve.

Input
The first line of the input file contains two integer numbers N and T (1 ≤ N ≤ 1000; 1 ≤ T ≤ 109), where N is the number of problems, T is the duration of the training. The second line contains N integer numbers ti (1 ≤ ti ≤ 3500), where ti is the time required to solve i-th problem. The third line contains integer number M (0 ≤ M ≤ 10000) — number of constraints. Each of the next M lines contains one constraint represented by pair of integer numbers ai, bi (1 ≤ ai,bi ≤ N; ai <> bi), denoting that the problem ai must be solved before the problem bi can be solved. It is guaranteed that tai ≤ tbi. All numbers in the input file are integer.

Output
On the first line of the output file print the maximal number of problems that the team can solve and the corresponding minimal penalty time. On the second line print numbers of problems that need to be solved in the order they must be solved. Problems are numbered 1 through N. If there are several solutions, output any of them.

Example(s)
sample input
sample output
1 1
1
0
1 1
1

sample input
sample output
3 10
1 1 1
3
1 2
2 3
3 1
0 0

sample input
sample output
4 2
1 2 1 2
1
1 3
2 3
1 3

=================
p367.ans3
======================
2 3
1 3

=================
p367.in1
======================
1 1
1
0

=================
p367.ans2
======================
0 0

=================
