AT_abc341_f [ABC341F] Breakdown

[problemUrl]: https://atcoder.jp/contests/abc341/tasks/abc341_f $ 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 $ 個ずつコマを置く。 操作を行う回数としてあり得る最大値を出力してください。 なお、どのように操作を行っても、有限回の操作の後にはグラフ上にコマが存在しない状態に至ることが証明出来ます。

入力は以下の形式で標準入力から与えられる。 > $ 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 $

答えを出力せよ。

### 制約 - 入力される値はすべて整数 - $ 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 $ ### Sample Explanation 1 以下の説明では、各頂点にあるコマの個数を、数列 $ 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 $ 回であり、これが操作を行う回数としてあり得る最大値です。 ### Sample Explanation 2 この入力例では、はじめからグラフ上にコマが存在しません。