E - プロジェクトの進行管理 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 433 点

問題文

高橋君はあるプロジェクトを進めており、1 から N までの番号が付けられた N 個のタスクをすべて完了させる必要があります。

プロジェクトは時刻 0 に開始します。各タスク i (1 \le i \le N) の所要時間は A_i であり、非負整数の開始時刻 S_i (S_i \ge 0) を決めて作業を開始すると、時刻 S_i + A_i に完了します（途中で作業を中断することはできません）。

前提関係を満たす限り、同時に任意の個数のタスクを並行して進めることができます。

タスクの間には M 個の前提関係が存在し、j 番目 (1 \le j \le M) の前提関係は「タスク V_j を開始するためには、タスク U_j が完了していなければならない（すなわち S_{V_j} \ge S_{U_j} + A_{U_j} を満たす必要がある）」というものです。

すべての前提関係を満たすように各タスクの開始時刻 S_1, S_2, \dots, S_N を決めるとき、すべてのタスクが完了する時刻 \max_{1 \le i \le N} (S_i + A_i) の最小値を求めてください。

ただし、すべての前提関係を満たすような開始時刻の組 (S_1, S_2, \dots, S_N) が存在しない場合は、その旨を報告してください。

制約

  • 1 \le N \le 2 \times 10^5
  • 0 \le M \le 10^5
  • 1 \le A_i \le 10^9 (1 \le i \le N)
  • 1 \le U_j, V_j \le N (1 \le j \le M)
  • U_j \ne V_j (1 \le j \le M)
  • (U_j, V_j) はすべて相異なる
  • 入力はすべて整数

入力

入力は以下の形式で与えられる。

N M
A_1 A_2 \dots A_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M

M = 0 の場合、前提関係を表す行は与えられない。

出力

すべてのタスクが完了する時刻の最小値を表す整数を 1 行で出力してください。

ただし、すべての前提関係を満たすような開始時刻の組が存在しない場合は、代わりに -1 を出力してください。

入力例 1

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

出力例 1

11

入力例 2

3 3
10 20 30
1 2
2 3
3 1

出力例 2

-1

入力例 3

10 11
1000000000 500000000 200000000 700000000 300000000 100000000 400000000 600000000 800000000 900000000
1 3
2 3
2 5
3 4
3 5
4 6
5 6
6 8
7 8
7 9
8 10

出力例 3

3500000000

入力例 4

20 25
12 45 78 23 90 34 56 67 89 12 34 56 78 90 23 45 67 89 12 34
1 5
1 6
2 6
2 7
3 7
3 8
4 8
5 9
5 10
6 10
6 11
7 11
7 12
8 12
9 13
10 14
11 15
12 16
13 17
14 18
15 19
16 20
17 20
18 20
19 20

出力例 4

370

入力例 5

1 0
1000000000

出力例 5

1000000000

Score : 433 pts

Problem Statement

Takahashi is managing a project and needs to complete all N tasks, numbered 1 through N.

The project starts at time 0. For each task i (1 \le i \le N), the time required is A_i. If work starts at a chosen non-negative integer start time S_i (S_i \ge 0), the task completes at time S_i + A_i (work cannot be interrupted midway).

Any number of tasks can be processed in parallel as long as the prerequisite constraints are satisfied.

There are M prerequisite constraints between the tasks. The j-th constraint (1 \le j \le M) states that "task U_j must be completed before task V_j can be started (that is, S_{V_j} \ge S_{U_j} + A_{U_j} must hold)."

When choosing the start times S_1, S_2, \dots, S_N for each task to satisfy all prerequisite constraints, find the minimum possible time at which all tasks are completed, \max_{1 \le i \le N} (S_i + A_i).

However, if there is no set of start times (S_1, S_2, \dots, S_N) that satisfies all prerequisite constraints, report that instead.

Constraints

  • 1 \le N \le 2 \times 10^5
  • 0 \le M \le 10^5
  • 1 \le A_i \le 10^9 (1 \le i \le N)
  • 1 \le U_j, V_j \le N (1 \le j \le M)
  • U_j \ne V_j (1 \le j \le M)
  • All pairs (U_j, V_j) are distinct.
  • All input values are integers.

Input

The input is given in the following format:

N M
A_1 A_2 \dots A_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M

If M = 0, no lines representing prerequisite constraints are given.

Output

Print a single line containing an integer representing the minimum possible time at which all tasks are completed.

However, if there is no set of start times that satisfies all prerequisite constraints, print -1 instead.

Sample Input 1

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

Sample Output 1

11

Sample Input 2

3 3
10 20 30
1 2
2 3
3 1

Sample Output 2

-1

Sample Input 3

10 11
1000000000 500000000 200000000 700000000 300000000 100000000 400000000 600000000 800000000 900000000
1 3
2 3
2 5
3 4
3 5
4 6
5 6
6 8
7 8
7 9
8 10

Sample Output 3

3500000000

Sample Input 4

20 25
12 45 78 23 90 34 56 67 89 12 34 56 78 90 23 45 67 89 12 34
1 5
1 6
2 6
2 7
3 7
3 8
4 8
5 9
5 10
6 10
6 11
7 11
7 12
8 12
9 13
10 14
11 15
12 16
13 17
14 18
15 19
16 20
17 20
18 20
19 20

Sample Output 4

370

Sample Input 5

1 0
1000000000

Sample Output 5

1000000000