F - Breakdown Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 475 点

問題文

N 個の頂点と M 本の辺からなる単純な無向グラフが与えられます。 i = 1, 2, \ldots, M について、i 番目の辺は頂点 u_i と頂点 v_i を結ぶ辺です。 また、i = 1, 2, \ldots, N について、頂点 i には正整数 W_i が割り当てられており、A_i 個のコマが置かれています。

グラフ上にコマが存在する限り、下記の操作を繰り返します。

  • まず、グラフ上のコマを 1 個選んで取り除き、そのコマが置かれていた頂点を x とおく。
  • x に隣接するいくつかの頂点からなる（空でも良い）集合 S であって、\sum_{y \in S} W_y \lt W_x であるものを選び、S に含まれる頂点それぞれに 1 個ずつコマを置く。

操作を行う回数としてあり得る最大値を出力してください。

なお、どのように操作を行っても、有限回の操作の後にはグラフ上にコマが存在しない状態に至ることが証明出来ます。

制約

  • 入力される値はすべて整数
  • 2 \leq N \leq 5000
  • 1 \leq M \leq \min \lbrace N(N-1)/2, 5000 \rbrace
  • 1 \leq u_i, v_i \leq N
  • u_i \neq v_i
  • i \neq j \implies \lbrace u_i, v_i \rbrace \neq \lbrace u_j, v_j \rbrace
  • 1 \leq W_i \leq 5000
  • 0 \leq A_i \leq 10^9

入力

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M
W_1 W_2 \ldots W_N
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

6 6
1 2
2 3
3 1
3 4
1 5
5 6
9 2 3 1 4 4
1 0 0 0 0 1

出力例 1

5

以下の説明では、各頂点にあるコマの個数を、数列 A = (A_1, A_2, \ldots, A_N) として表します。 はじめ、A = (1, 0, 0, 0, 0, 1) です。

下記の手順で操作を行うことを考えます。

  • 頂点 1 にあるコマを 1 個取り除き、頂点 2, 3 にコマを 1 個ずつ置く。その結果、A = (0, 1, 1, 0, 0, 1) となる。
  • 頂点 2 にあるコマを 1 個取り除く。その結果、A = (0, 0, 1, 0, 0, 1) となる。
  • 頂点 6 にあるコマを 1 個取り除く。その結果、A = (0, 0, 1, 0, 0, 0) となる。
  • 頂点 3 にあるコマを 1 個取り除き、頂点 2 にコマを 1 個置く。その結果、A = (0, 1, 0, 0, 0, 0) となる。
  • 頂点 2 にあるコマを 1 個取り除く。その結果、A = (0, 0, 0, 0, 0, 0) となる。

上記の手順で操作を行う回数は 5 回であり、これが操作を行う回数としてあり得る最大値です。

入力例 2

2 1
1 2
1 2
0 0

出力例 2

0

この入力例では、はじめからグラフ上にコマが存在しません。

入力例 3

10 20
4 8
1 10
1 7
5 9
9 10
8 10
7 5
1 4
7 3
8 7
2 8
5 8
4 2
5 1
7 2
8 3
3 4
8 9
7 10
2 3
25 5 1 1 16 5 98 3 21 1
35 39 32 11 35 37 14 29 36 1

出力例 3

1380

Score: 475 points

Problem Statement

You are given a simple undirected graph consisting of N vertices and M edges. For i = 1, 2, \ldots, M, the i-th edge connects vertices u_i and v_i. Also, for i = 1, 2, \ldots, N, vertex i is assigned a positive integer W_i, and there are A_i pieces placed on it.

As long as there are pieces on the graph, repeat the following operation:

  • First, choose and remove one piece from the graph, and let x be the vertex on which the piece was placed.
  • Choose a (possibly empty) set S of vertices adjacent to x such that \sum_{y \in S} W_y \lt W_x, and place one piece on each vertex in S.

Print the maximum number of times the operation can be performed.

It can be proved that, regardless of how the operation is performed, there will be no pieces on the graph after a finite number of iterations.

Constraints

  • All input values are integers.
  • 2 \leq N \leq 5000
  • 1 \leq M \leq \min \lbrace N(N-1)/2, 5000 \rbrace
  • 1 \leq u_i, v_i \leq N
  • u_i \neq v_i
  • i \neq j \implies \lbrace u_i, v_i \rbrace \neq \lbrace u_j, v_j \rbrace
  • 1 \leq W_i \leq 5000
  • 0 \leq A_i \leq 10^9

Input

The input is given from Standard Input in the following format:

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M
W_1 W_2 \ldots W_N
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

6 6
1 2
2 3
3 1
3 4
1 5
5 6
9 2 3 1 4 4
1 0 0 0 0 1

Sample Output 1

5

In the following explanation, let A = (A_1, A_2, \ldots, A_N) represent the numbers of pieces on the vertices. Initially, A = (1, 0, 0, 0, 0, 1).

Consider performing the operation as follows:

  • Remove one piece from vertex 1 and place one piece each on vertices 2 and 3. Now, A = (0, 1, 1, 0, 0, 1).
  • Remove one piece from vertex 2. Now, A = (0, 0, 1, 0, 0, 1).
  • Remove one piece from vertex 6. Now, A = (0, 0, 1, 0, 0, 0).
  • Remove one piece from vertex 3 and place one piece on vertex 2. Now, A = (0, 1, 0, 0, 0, 0).
  • Remove one piece from vertex 2. Now, A = (0, 0, 0, 0, 0, 0).

In this procedure, the operation is performed five times, which is the maximum possible number of times.

Sample Input 2

2 1
1 2
1 2
0 0

Sample Output 2

0

In this sample input, there are no pieces on the graph from the beginning.

Sample Input 3

10 20
4 8
1 10
1 7
5 9
9 10
8 10
7 5
1 4
7 3
8 7
2 8
5 8
4 2
5 1
7 2
8 3
3 4
8 9
7 10
2 3
25 5 1 1 16 5 98 3 21 1
35 39 32 11 35 37 14 29 36 1

Sample Output 3

1380