#include using namespace std; #include using namespace atcoder; using mint=atcoder::modint998244353; #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #define int long long templateusing pqmin=priority_queue,greater>; signed main(){ int N,M,P,Y;cin>>N>>M>>P>>Y; vector>> g(N); for(int i=0;i>a>>b>>c; a--;b--; g[a].push_back({b,c}); g[b].push_back({a,c}); } vector v(N,1e18); for(int i=0;i>d>>e; v[d-1]=e; } vector dist(N,1e18); dist[0]=0; pqmin> pq; pq.push({0,0}); while(pq.size()){ auto[cost,p]=pq.top();pq.pop(); if(dist[p]dist[p]+c){ dist[e]=dist[p]+c; pq.push({dist[e],e}); } } } int ans=0; for(int i=0;i(0,Y-dist[i]); ans=max(ans,tmp/v[i]); } cout<