E - サーバーネットワークの一斉アップデート 解説 /

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

配点 : 466 点

問題文

高橋君は N 台のサーバーからなる大規模ネットワークを管理しています。サーバーには 1 から N までの番号が付けられています。

ネットワークには M 本の一方通行の通信回線があり、i 番目の回線（1 \leq i \leq M）はサーバー U_i からサーバー V_i へデータを送信できます。同じ始点・終点の組を持つ回線が複数存在することもありますが、始点と終点が同じサーバーである回線（自己ループ）は存在しません。各サーバー j（1 \leq j \leq N）には現在のセキュリティレベルが整数値 W_j として定められています。

ここで、サーバー x からサーバー y に「到達可能」であるとは、サーバー x から回線の向きに沿って 1 本以上の回線を辿ることでサーバー y に到達できることを意味します。x = y の場合も例外ではなく、サーバー x から x 自身に到達可能であるとは、x から出発して 1 本以上の回線を辿って再び x に戻れること、すなわち x を含む有向閉路が存在することを意味します。

高橋君はネットワーク全体のセキュリティを向上させるため、以下の操作を何回でも（0 回でもよい）行えます。毎回の操作で選ぶサーバーは 1 から N のいずれでもよく、同じサーバーを複数回選ぶこともできます。

操作： サーバー v を 1 つ選ぶ。v から到達可能かつ v へも到達可能であるようなサーバー u 全体の集合を S(v) とする（v 自身も、v から v へ到達可能である場合に限り S(v) に含まれる）。S(v) が空でない場合、S(v) に含まれるすべてのサーバーのセキュリティレベルを一律に 1 増加させる。S(v) が空の場合、何も起こらない。

すなわち、v を含む有向閉路が存在するとき、S(v) は v と互いに到達可能なサーバー全体の集合（v を含む強連結成分）と一致し、これらのサーバーすべてのセキュリティレベルが 1 増加します。v を含む有向閉路が存在しないとき、S(v) は空集合となり、操作を行っても何も変化しません。

各サーバー j（1 \leq j \leq N）には「要求水準」として整数値 T_j が定められています。すべてのサーバー j についてセキュリティレベルが T_j 以上であるとき、ネットワーク全体が基準達成であるといいます。

高橋君の目標は、操作を繰り返すことでネットワーク全体を基準達成の状態にすることです。必要な操作の合計回数の最小値を求めてください。

ただし、操作をどのように行っても基準達成にできない場合は -1 を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 0 \leq W_j \leq 10^9 (1 \leq j \leq N)
  • 0 \leq T_j \leq 10^9 (1 \leq j \leq N)
  • 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
  • U_i \neq V_i (1 \leq i \leq M)
  • 入力はすべて整数である

入力

N M
W_1 W_2 \ldots W_N
T_1 T_2 \ldots T_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • 1 行目には、サーバーの台数 N と回線の本数 M がスペース区切りで与えられる。
  • 2 行目には、各サーバーの初期セキュリティレベル W_1, W_2, \ldots, W_N がスペース区切りで与えられる。
  • 3 行目には、各サーバーの要求水準 T_1, T_2, \ldots, T_N がスペース区切りで与えられる。
  • 4 行目から M 行にわたり、各回線の始点 U_i と終点 V_i がスペース区切りで与えられる。

出力

ネットワーク全体を基準達成にするために必要な操作の最小回数を 1 行で出力せよ。達成不可能な場合は -1 を出力せよ。

なお、答えは非常に大きくなることがあるため、64 bit 整数型を使用することを推奨する。

入力例 1

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

出力例 1

3

入力例 2

3 2
0 0 1
2 1 5
1 2
2 1

出力例 2

-1

入力例 3

10 14
10 5 7 1 2 100 0 4 10 3
12 9 7 3 6 50 5 8 12 3
1 2
2 3
3 1
3 4
4 5
5 4
5 6
6 7
7 8
8 9
9 7
2 4
4 5
8 10

出力例 3

13

入力例 4

20 31
100 95 98 90 0 10 5 50 1 2 3 4 5 1000 999 7 0 0 0 123
101 100 99 97 3 12 8 50 10 5 8 4 20 1000 1005 6 1 2 3 123
1 2
2 3
3 4
4 1
1 3
2 4
5 6
6 7
7 5
5 7
9 10
10 11
11 12
12 13
13 9
9 11
10 12
14 15
15 14
17 18
18 19
19 17
17 19
4 5
3 8
7 9
8 9
13 14
15 16
12 17
19 20

出力例 4

34

入力例 5

1 0
0
0

出力例 5

0

Score : 466 pts

Problem Statement

Takahashi manages a large-scale network consisting of N servers. The servers are numbered from 1 to N.

The network has M one-way communication links. The i-th link (1 \leq i \leq M) can transmit data from server U_i to server V_i. There may be multiple links with the same source-destination pair, but there are no links where the source and destination are the same server (no self-loops). Each server j (1 \leq j \leq N) has a current security level defined as an integer value W_j.

Here, server x is said to be "reachable" to server y if it is possible to reach server y from server x by following one or more links in their directed order. The case x = y is no exception: server x being reachable to itself means that starting from x, one can follow one or more links and return to x, i.e., there exists a directed cycle containing x.

To improve the security of the entire network, Takahashi can perform the following operation any number of times (including 0 times). In each operation, any server from 1 to N may be chosen, and the same server may be chosen multiple times.

Operation: Choose one server v. Let S(v) be the set of all servers u such that u is reachable from v and v is reachable from u (v itself is included in S(v) only if v is reachable from v). If S(v) is non-empty, increase the security level of all servers in S(v) by 1. If S(v) is empty, nothing happens.

In other words, when a directed cycle containing v exists, S(v) coincides with the set of all servers mutually reachable with v (the strongly connected component containing v), and the security levels of all these servers are increased by 1. When no directed cycle containing v exists, S(v) is the empty set, and performing the operation causes no change.

For each server j (1 \leq j \leq N), a "required level" is defined as an integer value T_j. The entire network is said to have met the standard when the security level of every server j is at least T_j.

Takahashi's goal is to bring the entire network to a state where the standard is met by repeating operations. Find the minimum total number of operations required.

If it is impossible to meet the standard regardless of how operations are performed, output -1.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 0 \leq W_j \leq 10^9 (1 \leq j \leq N)
  • 0 \leq T_j \leq 10^9 (1 \leq j \leq N)
  • 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
  • U_i \neq V_i (1 \leq i \leq M)
  • All input values are integers

Input

N M
W_1 W_2 \ldots W_N
T_1 T_2 \ldots T_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • The first line contains the number of servers N and the number of links M, separated by a space.
  • The second line contains the initial security levels W_1, W_2, \ldots, W_N of each server, separated by spaces.
  • The third line contains the required levels T_1, T_2, \ldots, T_N of each server, separated by spaces.
  • From the fourth line onward, M lines each contain the source U_i and destination V_i of each link, separated by a space.

Output

Output in one line the minimum number of operations required to bring the entire network to a state where the standard is met. If it is impossible, output -1.

Note that the answer may be very large, so it is recommended to use a 64-bit integer type.

Sample Input 1

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

Sample Output 1

3

Sample Input 2

3 2
0 0 1
2 1 5
1 2
2 1

Sample Output 2

-1

Sample Input 3

10 14
10 5 7 1 2 100 0 4 10 3
12 9 7 3 6 50 5 8 12 3
1 2
2 3
3 1
3 4
4 5
5 4
5 6
6 7
7 8
8 9
9 7
2 4
4 5
8 10

Sample Output 3

13

Sample Input 4

20 31
100 95 98 90 0 10 5 50 1 2 3 4 5 1000 999 7 0 0 0 123
101 100 99 97 3 12 8 50 10 5 8 4 20 1000 1005 6 1 2 3 123
1 2
2 3
3 4
4 1
1 3
2 4
5 6
6 7
7 5
5 7
9 10
10 11
11 12
12 13
13 9
9 11
10 12
14 15
15 14
17 18
18 19
19 17
17 19
4 5
3 8
7 9
8 9
13 14
15 16
12 17
19 20

Sample Output 4

34

Sample Input 5

1 0
0
0

Sample Output 5

0