헬스장 운동 순서와 최소 소요 시간

문제

헬스장 트레이너가 회원의 하루 운동 계획을 짜고 있다. 운동은 1번부터 N번까지 N개이고, i번 운동을 마치는 데에는 정확히 t_i분이 걸린다. 일부 운동 사이에는 선행 관계가 있다. 선행 관계 "a b"는 a번 운동을 완전히 마친 뒤에야 b번 운동을 시작할 수 있다는 뜻이다. 선행 관계는 M개 주어지며, 같은 쌍이 여러 번 주어질 수도 있다. 한 운동은 자기 자신의 선행 운동이 될 수 없다. 트레이너는 두 가지를 알고 싶다. 첫째, 회원 한 명이 운동을 하나씩 차례로 할 때의 순서다. 선행 관계를 모두 지키면서, 매번 지금 시작할 수 있는 운동이 여럿이면 번호가 가장 작은 운동을 고른다. 이렇게 정해지는 운동 번호의 나열을 구한다. 둘째, 회원이 충분히 많아 시작할 수 있는 운동을 모두 동시에 진행할 수 있다고 할 때, 모든 운동을 마치는 데 걸리는 최소 시간이다. 어떤 운동은 선행 운동이 모두 끝나는 즉시 시작하며, 운동의 시작 시각은 선행 운동들이 끝난 시각 중 가장 늦은 시각이다. 선행 운동이 없는 운동은 시각 0에 시작한다. 선행 관계에 순환이 있어 모든 운동을 끝낼 수 없다면 -1만 한 줄에 출력한다.

입력

첫 줄에 N과 M이 공백으로 주어진다. (1 ≤ N ≤ 20000, 0 ≤ M ≤ 20000) 둘째 줄에 t_1, ..., t_N이 공백으로 주어진다. (1 ≤ t_i ≤ 999, 정수) 이어서 M개의 줄에 선행 관계 a b가 주어진다. (1 ≤ a, b ≤ N, a ≠ b)

출력

모든 운동을 끝낼 수 있으면 첫 줄에 운동 번호 N개를 공백으로 구분해 출력하고, 둘째 줄에 최소 소요 시간을 출력한다. 끝낼 수 없으면 -1만 출력한다.

5 4
3 2 4 1 5
1 3
2 3
3 4
5 4

1 2 3 5 4
8

3 3
1 1 1
1 2
2 3
3 1

-1

1 0
7

1
7

출처: Devin.KR 자체 제작