A - City with Power Shortage Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は N 個の都市からなる地域の電力網を管理しています。各都市には 1 から N までの番号が付けられており、都市 i には正常に機能するために必要な電力量（需要量） S_i が定められています。

この地域には M 本の送電線があり、各送電線は 2 つの都市を双方向に結んでいます。 j 番目の送電線は都市 U_j と都市 V_j を結び、送電容量 W_j を持ちます。各送電線は、結んでいる 2 つの都市のそれぞれに対して、送電容量の分だけ電力を供給することができます。

都市 i に供給可能な電力量 T_i を、都市 i を端点とするすべての送電線の送電容量の合計として定めます。すなわち、都市 i を端点とする送電線の送電容量が W_{j_1}, W_{j_2}, \ldots, W_{j_k} であるとき、 T_i = W_{j_1} + W_{j_2} + \cdots + W_{j_k} です。都市 i を端点とする送電線が 1 本も存在しない場合は T_i = 0 とします。

都市 i が「電力不足の都市」であるとは、 T_i < S_i が成り立つことを意味します。

電力不足の都市の数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq S_i \leq 10^9 （1 \leq i \leq N）
  • 1 \leq U_j < V_j \leq N （1 \leq j \leq M）
  • 1 \leq W_j \leq 10^9 （1 \leq j \leq M）
  • 同じ都市の組を結ぶ送電線は高々 1 本である（すなわち、(U_j, V_j) の組はすべて異なる）
  • 入力はすべて整数である

入力

N M
S_1 S_2 \ldots S_N
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • 1 行目には、都市の数を表す N と送電線の数を表す M が、スペース区切りで与えられる。
  • 2 行目には、各都市の需要量を表す S_1, S_2, \ldots, S_N が、スペース区切りで与えられる。
  • 3 行目から M 行にわたり、送電線の情報が与えられる。
  • 2 + j 行目では、 j 番目の送電線が結ぶ都市 U_j と V_j 、および送電容量 W_j が、スペース区切りで与えられる。

出力

電力不足の都市の数を 1 行で出力せよ。

入力例 1

4 3
10 3 5 8
1 2 4
2 3 6
3 4 2

出力例 1

2

入力例 2

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

出力例 2

0

入力例 3

6 5
10 20 15 8 30 5
1 2 7
2 3 10
3 4 5
4 5 3
1 6 6

出力例 3

2

入力例 4

10 8
100 50 200 30 80 60 150 40 90 10
1 2 25
2 3 30
3 4 50
4 5 20
5 6 35
6 7 40
7 8 60
9 10 5

出力例 4

6

入力例 5

1 0
1

出力例 5

1

Score : 266 pts

Problem Statement

Takahashi manages the power grid of a region consisting of N cities. Each city is numbered from 1 to N, and city i has a required power amount (demand) S_i needed to function properly.

There are M power transmission lines in this region, each connecting two cities bidirectionally. The j-th transmission line connects city U_j and city V_j and has a transmission capacity of W_j. Each transmission line can supply power equal to its transmission capacity to each of the two cities it connects.

The power amount T_i that can be supplied to city i is defined as the sum of the transmission capacities of all transmission lines that have city i as an endpoint. That is, if the transmission capacities of the transmission lines with city i as an endpoint are W_{j_1}, W_{j_2}, \ldots, W_{j_k}, then T_i = W_{j_1} + W_{j_2} + \cdots + W_{j_k}. If there are no transmission lines with city i as an endpoint, then T_i = 0.

City i is called a "power-deficient city" if T_i < S_i holds.

Find the number of power-deficient cities.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq U_j < V_j \leq N (1 \leq j \leq M)
  • 1 \leq W_j \leq 10^9 (1 \leq j \leq M)
  • There is at most one transmission line connecting the same pair of cities (i.e., all pairs (U_j, V_j) are distinct)
  • All input values are integers

Input

N M
S_1 S_2 \ldots S_N
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • The first line contains N, the number of cities, and M, the number of transmission lines, separated by a space.
  • The second line contains the demand of each city S_1, S_2, \ldots, S_N, separated by spaces.
  • The following M lines provide information about the transmission lines.
  • The (2 + j)-th line contains the cities U_j and V_j connected by the j-th transmission line, and the transmission capacity W_j, separated by spaces.

Output

Output the number of power-deficient cities in one line.

Sample Input 1

4 3
10 3 5 8
1 2 4
2 3 6
3 4 2

Sample Output 1

2

Sample Input 2

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

Sample Output 2

0

Sample Input 3

6 5
10 20 15 8 30 5
1 2 7
2 3 10
3 4 5
4 5 3
1 6 6

Sample Output 3

2

Sample Input 4

10 8
100 50 200 30 80 60 150 40 90 10
1 2 25
2 3 30
3 4 50
4 5 20
5 6 35
6 7 40
7 8 60
9 10 5

Sample Output 4

6

Sample Input 5

1 0
1

Sample Output 5

1