AT_tkppc2015_h 私、木になります (I become a tree)

[problemUrl]: https://atcoder.jp/contests/tkppc/tasks/tkppc2015_h 本校に戻って次の部活を覗いてみると、そこにでは少女がウィスキーボンボンを食べていた。 そしてjoisinoお姉ちゃんを見つけると、一緒にゲームをしませんかと言った。 joisinoお姉ちゃんはゲームが大好きなので、もちろん一緒にすることにした。 そして『私、木になります』というゲームをすることになった。 このゲームでは$ N $個の都市と$ M $本の道を使用する。 はじめ、$ N $個の都市は$ M $本の道によって互いに行き来可能なように結ばれている。 このとき、道$ i(1\ ≦\ i\ ≦\ M) $は都市$ A_i(1\ ≦\ A_i\ ≦\ N) $と$ B_i(1\ ≦\ B_i\ ≦\ N) $を結んでいる。 そして都市同士が互いに行き来可能なまま道を取り除いていくというゲームである。 彼女は非常に頭が良いので、ゲームが始まる前からどの道をどのタイミングで取り除くかの計画を立てている。 この計画は$ Q $個の操作で構成されていて、$ i(1\ ≦\ i\ ≦\ Q) $番目の操作では道$ D_i(1\ ≦\ D_i\ ≦\ M) $を取り除こうとする。 また、取り除く道はゲーム開始時にあるものから選ばれていて、同じ道は複数回取り除かないようになっている。 しかし今、彼女はウィスキーボンボンを食べて少し酔っているので、この計画通りに道を取り除いていくとゲームのルールに違反してしまうことがある。 また、彼女はそれぞれの操作iについて重要性$ G_i $というものを持っている。 そして操作$ i $が失敗した場合、すなわち操作$ i $をすると都市同士が互いに行き来可能でなくなるため、その操作を行わない場合に彼女は$ G_i $だけ落ち込んでしまう。 よって彼女はゲーム終了時には失敗した操作の重要度の合計だけ落ち込んでいる。 joisinoお姉ちゃんはあまり彼女に落ち込んでほしくないので、ゲーム中の好きなタイミングで$ P $本以下の道を付け加えることにした。 ただしゲーム開始時に1本の道で結ばれていた2つの都市の間には道を付け加えることができない。 このことを行ったとき、joisinoお姉ちゃんはゲーム終了時に彼女がどれだけ落ち込むことになるかの最小値を計算することにした。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ Q $ $ P $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ ： $ A_M $ $ B_M $ $ D_1 $ $ G_1 $ $ D_2 $ $ G_2 $ ： $ D_Q $ $ G_Q $ - $ 1 $行目には、都市の数$ N(1\ ≦\ N\ ≦\ 10^5) $とゲーム開始時の道の数$ M(N-1\ ≦\ M\ ≦\ 3*10^5) $と操作の回数$ Q(1\ ≦\ Q\ ≦\ M) $と付け加えてよい道の数$ P(0\ ≦\ P\ ≦\ 10^9) $が空白区切りで与えられる。 - $ 2 $行目からの$ M $行のうち$ i $行目には$ i $番目の道の情報が書かれており、$ A_i $と$ B_i $が空白区切りで与えられる。 - $ M+1 $行目からの$ Q $行のうち$ i $行目には$ i $番目の操作の情報が書かれており、$ D_i $と$ G_i(1\ ≦\ G_i\ ≦\ 10^9) $が空白区切りで与えられる。 - $ A_i\ ≠\ B_i $が保証されている。 - $ i\ ≠\ j $において$ A_i\ ≠\ A_j $または$ B_i\ ≠\ B_j $が保証されている。 - $ i\ ≠\ j $において$ D_i\ ≠\ D_j $が保証されている。

ゲーム終了時の彼女の落ち込みの最小値を答えよ。 出力の末尾にも改行を入れること。

### 配点 この問題には部分点がある。 - データセット1は、$ N\ ≦\ 10^4 $、$ M\ ≦\ 10^4 $、$ P\ =\ 0 $を満たし、これに正解すると10点が得られる。 - データセット2は、$ P\ =\ 0 $を満たし、これに正解すると10点が得られる。 - データセット3では追加の制約はなく、これに正解すると120点が得られる。 ### Sample Explanation 1 この場合、はじめは上の図のように都市同士はつながっていて、最終的には下の図のような形になる。このとき彼女は道$ 2 $を取り除くことができず、ゲーム終了時に彼女は$ 10 $だけ落ち込んでいる。 !\[\](/img/other/tsukukoma2015/asasffewe/g3.jpg)!\[\](/img/other/tsukukoma2015/asasffewe/g4.jpg) ### Sample Explanation 2 \### 出力例2 ``` 11 ``` この場合、はじめは上の図のように都市同士はつながっていて、操作$ 2 $を行う前に都市$ 1 $と都市$ 4 $の間に道を作ることで、最終的には下の図のような形になる。このとき彼女は道$ 3 $を取り除くことができず、ゲーム終了時に彼女は$ 11 $だけ落ち込んでいる。なお、このケースはデータセット3に含まれている。 !\[\](/img/other/tsukukoma2015/asasffewe/g5.jpg)!\[\](/img/other/tsukukoma2015/asasffewe/g6.jpg) このテストケースはデータセット3に含まれている。