AT_arc098_d [ARC098F] Donation

[problemUrl]: https://atcoder.jp/contests/arc098/tasks/arc098_d $ N $ 頂点 $ M $ 辺の連結な単純無向グラフがあります。 頂点には $ 1 $ から $ N $ の番号が、辺には $ 1 $ から $ M $ の番号がついています。 辺 $ i $ は頂点 $ U_i $ と頂点 $ V_i $ を結んでいます。 また、頂点 $ i $ には二つの整数 $ A_i $, $ B_i $ が定められています。 あなたは、このグラフ上で次のようなゲームをします。 まず初めに、$ W $ 円を持った状態で好きな頂点に立つ。 ただし、立つ頂点を $ s $ としたとき、$ A_s\ \leq\ W $ でなくてはならない。 その後、以下の $ 2 $ 種類の操作を好きな順序で好きなだけ繰り返す。 - 今いる頂点と直接辺で結ばれている頂点の中から一つ好きなものを選び、その頂点を $ v $ とする。そして、頂点 $ v $ に移動する。ただし、移動する際の所持金は $ A_v $ 円以上でなくてはならない。 - 今いる頂点を $ v $ としたとき、$ B_v $ 円を頂点 $ v $ に寄付する。このとき、所持金が $ 0 $ 円未満になってはならない。 このゲームは、すべての頂点に $ 1 $ 度ずつ寄付をするとクリアになります。 このゲームのクリアが可能となる、最小の初期の所持金 $ W $ を求めてください。

N/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 10^5 $ - $ N-1\ \leq\ M\ \leq\ 10^5 $ - $ 1\ \leq\ A_i,B_i\ \leq\ 10^9 $ - $ 1\ \leq\ U_i\