#include using namespace std; const long long INF = (1ll<<61)-1; int main(void){ //cin.tie(nullptr); //ios::sync_with_stdio(false); long long N,K,M,P; cin >> N >> K >> M >> P; vector> G(N); for(int i=0;i> u >> v; u--;v--; G[u].push_back(v); G[v].push_back(u); } vector S(N),X(K); for(int i=0;i> S[i]; } for(int i=0;i> X[i]; X[i]--; } // {イベントが起こる日,イベントの種類,起こる頂点} priority_queue< array, vector>, greater> > que; long long Ans = 0; //回復したか vector recovered(N,false); //検疫が入ったか vector quarantined(N,false); //いま感染しているか vector infected(N,false); //0: 回復 1: 隣に感染 2:検疫 for(int i=0;i q = que.top(); que.pop(); //検疫が入った場合その後一切のアクションを起こさない if(quarantined[q[2]])continue; if(q[1] == 0){ //回復 infected[q[2]] = false; recovered[q[2]] = true; }else if(q[1] == 1){ //隣にうつす for(long long e:G[q[2]]){ if(recovered[e] || quarantined[e])continue; //すでにかかっていた場合検疫送り if(infected[e]){ que.push({q[0],2,e}); }else{ infected[e] = true; que.push({q[0]+P,0,e}); que.push({q[0]+S[e],1,e}); } } }else{ //検疫 Ans++; infected[q[2]] = false; quarantined[q[2]] = true; } } cout << Ans << endl; return 0; }