/ 
Time Limit: 3 sec / Memory Limit: 256 MB
問題文
本校に戻って次の部活を覗いてみると、そこにでは少女がウィスキーボンボンを食べていた。
そして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点が得られる。
出力
ゲーム終了時の彼女の落ち込みの最小値を答えよ。 出力の末尾にも改行を入れること。
入力例1
3 3 2 0 3 1 2 3 2 1 3 15 2 10
出力例1
10
この場合、はじめは上の図のように都市同士はつながっていて、最終的には下の図のような形になる。このとき彼女は道2を取り除くことができず、ゲーム終了時に彼女は10だけ落ち込んでいる。
入力例2
4 4 3 1 2 1 2 3 2 4 3 1 4 7 1 17 3 11
出力例2
11
この場合、はじめは上の図のように都市同士はつながっていて、操作2を行う前に都市1と都市4の間に道を作ることで、最終的には下の図のような形になる。このとき彼女は道3を取り除くことができず、ゲーム終了時に彼女は11だけ落ち込んでいる。なお、このケースはデータセット3に含まれている。
入力例3
4 6 4 5 3 1 2 1 3 4 4 1 2 3 2 4 5 23 3 18 6 5 4 14
出力例3
14
このテストケースはデータセット3に含まれている。