#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
class unionfind{
public:
int* o;
int* r;
void init(int n){
o = new int[n + 10];
r = new int[n + 10];
for (int i = 0; i < n + 10; i++){
o[i] = -1;
r[i] = 0;
}
}
int find(int n){
if (o[n] < 0) return n;
else return o[n] = find(o[n]);
}
void unit(int a, int b){
if (r[a] == r[b]){
r[a]++;
o[b] = a;
}
else if (r[a] > r[b]) o[b] = a;
else o[a] = b;
}
void del(){
delete[] o;
delete[] r;
}
};
pair<int, int> miti[3333333];
ll gg[3333333];
int jun[3333333];
bool ok[3333333];
vector<int> mw[1111111];
bool table[1111111];
int main(){
int n, m, q, p;
scanf("%d%d%d%d", &n, &m, &q, &p);
for (int i = 0; i < m; i++){
int a, b;
scanf("%d%d", &a, &b);
a--;
b--;
miti[i] = make_pair(a, b);
gg[i] = 0;
mw[a].push_back(b);
mw[b].push_back(a);
}
for (int i = 0; i < q; i++){
int d;
ll g;
scanf("%d%lld", &d, &g);
d--;
jun[i] = d;
gg[d] = g;
}
unionfind ufa;
ufa.init(n);
for (int i = 0; i < m; i++){
if (gg[i] == 0){
int w1 = ufa.find(miti[i].first);
int w2 = ufa.find(miti[i].second);
if (w1 != w2){
ufa.unit(w1, w2);
}
}
}
for (int i = q - 1; i >= 0; i--){
pair<int, int> w = miti[jun[i]];
int w1 = ufa.find(w.first);
int w2 = ufa.find(w.second);
if (w1 != w2){
ufa.unit(w1, w2);
ok[i] = false;
}
else ok[i] = true;
}
ufa.del();
ufa.init(n);
for (int i = 0; i < q; i++){
pair<int, int> w = miti[jun[i]];
int w1 = ufa.find(w.first);
int w2 = ufa.find(w.second);
if (w1 == w2 || ok[i]) gg[jun[i]] = -1;
else ufa.unit(w1, w2);
}
ufa.del();
ufa.init(n + 1);
for (int i = 0; i < n; i++){
if (n - mw[i].size() < 3000){
for (int j = 0; j < n; j++) table[j] = true;
int l = mw[i].size();
for (int j = 0; j < l; j++) table[mw[i][j]] = false;
for (int j = 0; j < n; j++){
if (table[j]){
int w1 = ufa.find(i);
int w2 = ufa.find(j);
if (w1 != w2){
ufa.unit(w1, w2);
}
}
}
}
else{
int w1 = ufa.find(i);
int w2 = ufa.find(n);
if (w1 != w2){
ufa.unit(w1, w2);
}
}
}
ll res = 0;
vector<ll> vw;
vector<pair<ll, int> > vv;
for (int i = 0; i < m; i++){
if (gg[i] >= 0){
int w1 = ufa.find(miti[i].first);
int w2 = ufa.find(miti[i].second);
if (w1 != w2) vv.push_back(make_pair(gg[i], i));
else vw.push_back(gg[i]);
}
}
sort(vv.begin(), vv.end());
int lw = vv.size();
for (int i = 0; i < lw; i++){
int w1 = ufa.find(miti[vv[i].second].first);
int w2 = ufa.find(miti[vv[i].second].second);
if (w1 != w2){
ufa.unit(w1, w2);
res += vv[i].first;
}
else vw.push_back(vv[i].first);
}
sort(vw.begin(), vw.end());
lw = vw.size();
for (int i = 0; i < lw - p; i++){
res += vw[i];
}
printf("%lld\n", res);
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPHZlY3Rvcj4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKCmNsYXNzIHVuaW9uZmluZHsKcHVibGljOgoJaW50KiBvOwoJaW50KiByOwoKCXZvaWQgaW5pdChpbnQgbil7CgkJbyA9IG5ldyBpbnRbbiArIDEwXTsKCQlyID0gbmV3IGludFtuICsgMTBdOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgbiArIDEwOyBpKyspewoJCQlvW2ldID0gLTE7CgkJCXJbaV0gPSAwOwoJCX0KCX0KCglpbnQgZmluZChpbnQgbil7CgkJaWYgKG9bbl0gPCAwKSByZXR1cm4gbjsKCQllbHNlIHJldHVybiBvW25dID0gZmluZChvW25dKTsKCX0KCgl2b2lkIHVuaXQoaW50IGEsIGludCBiKXsKCQlpZiAoclthXSA9PSByW2JdKXsKCQkJclthXSsrOwoJCQlvW2JdID0gYTsKCQl9CgkJZWxzZSBpZiAoclthXSA+IHJbYl0pIG9bYl0gPSBhOwoJCWVsc2Ugb1thXSA9IGI7Cgl9CgoJdm9pZCBkZWwoKXsKCQlkZWxldGVbXSBvOwoJCWRlbGV0ZVtdIHI7Cgl9Cn07CgpwYWlyPGludCwgaW50PiBtaXRpWzMzMzMzMzNdOwpsbCBnZ1szMzMzMzMzXTsKaW50IGp1blszMzMzMzMzXTsKYm9vbCBva1szMzMzMzMzXTsKdmVjdG9yPGludD4gbXdbMTExMTExMV07CmJvb2wgdGFibGVbMTExMTExMV07CgppbnQgbWFpbigpewoJaW50IG4sIG0sIHEsIHA7CglzY2FuZigiJWQlZCVkJWQiLCAmbiwgJm0sICZxLCAmcCk7Cglmb3IgKGludCBpID0gMDsgaSA8IG07IGkrKyl7CgkJaW50IGEsIGI7CgkJc2NhbmYoIiVkJWQiLCAmYSwgJmIpOwoJCWEtLTsKCQliLS07CgkJbWl0aVtpXSA9IG1ha2VfcGFpcihhLCBiKTsKCQlnZ1tpXSA9IDA7CgkJbXdbYV0ucHVzaF9iYWNrKGIpOwoJCW13W2JdLnB1c2hfYmFjayhhKTsKCX0KCWZvciAoaW50IGkgPSAwOyBpIDwgcTsgaSsrKXsKCQlpbnQgZDsKCQlsbCBnOwoJCXNjYW5mKCIlZCVsbGQiLCAmZCwgJmcpOwoJCWQtLTsKCQlqdW5baV0gPSBkOwoJCWdnW2RdID0gZzsKCX0KCXVuaW9uZmluZCB1ZmE7Cgl1ZmEuaW5pdChuKTsKCWZvciAoaW50IGkgPSAwOyBpIDwgbTsgaSsrKXsKCQlpZiAoZ2dbaV0gPT0gMCl7CgkJCWludCB3MSA9IHVmYS5maW5kKG1pdGlbaV0uZmlyc3QpOwoJCQlpbnQgdzIgPSB1ZmEuZmluZChtaXRpW2ldLnNlY29uZCk7CgkJCWlmICh3MSAhPSB3Mil7CgkJCQl1ZmEudW5pdCh3MSwgdzIpOwoJCQl9CgkJfQoJfQoJZm9yIChpbnQgaSA9IHEgLSAxOyBpID49IDA7IGktLSl7CgkJcGFpcjxpbnQsIGludD4gdyA9IG1pdGlbanVuW2ldXTsKCQlpbnQgdzEgPSB1ZmEuZmluZCh3LmZpcnN0KTsKCQlpbnQgdzIgPSB1ZmEuZmluZCh3LnNlY29uZCk7CgkJaWYgKHcxICE9IHcyKXsKCQkJdWZhLnVuaXQodzEsIHcyKTsKCQkJb2tbaV0gPSBmYWxzZTsKCQl9CgkJZWxzZSBva1tpXSA9IHRydWU7Cgl9Cgl1ZmEuZGVsKCk7Cgl1ZmEuaW5pdChuKTsKCWZvciAoaW50IGkgPSAwOyBpIDwgcTsgaSsrKXsKCQlwYWlyPGludCwgaW50PiB3ID0gbWl0aVtqdW5baV1dOwoJCWludCB3MSA9IHVmYS5maW5kKHcuZmlyc3QpOwoJCWludCB3MiA9IHVmYS5maW5kKHcuc2Vjb25kKTsKCQlpZiAodzEgPT0gdzIgfHwgb2tbaV0pIGdnW2p1bltpXV0gPSAtMTsKCQllbHNlIHVmYS51bml0KHcxLCB3Mik7Cgl9Cgl1ZmEuZGVsKCk7Cgl1ZmEuaW5pdChuICsgMSk7Cglmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKyl7CgkJaWYgKG4gLSBtd1tpXS5zaXplKCkgPCAzMDAwKXsKCQkJZm9yIChpbnQgaiA9IDA7IGogPCBuOyBqKyspIHRhYmxlW2pdID0gdHJ1ZTsKCQkJaW50IGwgPSBtd1tpXS5zaXplKCk7CgkJCWZvciAoaW50IGogPSAwOyBqIDwgbDsgaisrKSB0YWJsZVttd1tpXVtqXV0gPSBmYWxzZTsKCQkJZm9yIChpbnQgaiA9IDA7IGogPCBuOyBqKyspewoJCQkJaWYgKHRhYmxlW2pdKXsKCQkJCQlpbnQgdzEgPSB1ZmEuZmluZChpKTsKCQkJCQlpbnQgdzIgPSB1ZmEuZmluZChqKTsKCQkJCQlpZiAodzEgIT0gdzIpewoJCQkJCQl1ZmEudW5pdCh3MSwgdzIpOwoJCQkJCX0KCQkJCX0KCQkJfQoJCX0KCQllbHNlewoJCQlpbnQgdzEgPSB1ZmEuZmluZChpKTsKCQkJaW50IHcyID0gdWZhLmZpbmQobik7CgkJCWlmICh3MSAhPSB3Mil7CgkJCQl1ZmEudW5pdCh3MSwgdzIpOwoJCQl9CgkJfQoJfQoJbGwgcmVzID0gMDsKCXZlY3RvcjxsbD4gdnc7Cgl2ZWN0b3I8cGFpcjxsbCwgaW50PiA+IHZ2OwoJZm9yIChpbnQgaSA9IDA7IGkgPCBtOyBpKyspewoJCWlmIChnZ1tpXSA+PSAwKXsKCQkJaW50IHcxID0gdWZhLmZpbmQobWl0aVtpXS5maXJzdCk7CgkJCWludCB3MiA9IHVmYS5maW5kKG1pdGlbaV0uc2Vjb25kKTsKCQkJaWYgKHcxICE9IHcyKSB2di5wdXNoX2JhY2sobWFrZV9wYWlyKGdnW2ldLCBpKSk7CgkJCWVsc2UgdncucHVzaF9iYWNrKGdnW2ldKTsKCQl9Cgl9Cglzb3J0KHZ2LmJlZ2luKCksIHZ2LmVuZCgpKTsKCWludCBsdyA9IHZ2LnNpemUoKTsKCWZvciAoaW50IGkgPSAwOyBpIDwgbHc7IGkrKyl7CgkJaW50IHcxID0gdWZhLmZpbmQobWl0aVt2dltpXS5zZWNvbmRdLmZpcnN0KTsKCQlpbnQgdzIgPSB1ZmEuZmluZChtaXRpW3Z2W2ldLnNlY29uZF0uc2Vjb25kKTsKCQlpZiAodzEgIT0gdzIpewoJCQl1ZmEudW5pdCh3MSwgdzIpOwoJCQlyZXMgKz0gdnZbaV0uZmlyc3Q7CgkJfQoJCWVsc2UgdncucHVzaF9iYWNrKHZ2W2ldLmZpcnN0KTsKCX0KCXNvcnQodncuYmVnaW4oKSwgdncuZW5kKCkpOwoJbHcgPSB2dy5zaXplKCk7Cglmb3IgKGludCBpID0gMDsgaSA8IGx3IC0gcDsgaSsrKXsKCQlyZXMgKz0gdndbaV07Cgl9CglwcmludGYoIiVsbGRcbiIsIHJlcyk7CglyZXR1cm4gMDsKfQo=