#include using namespace std; using p = pair; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, P, Y, ans = 0; cin >> N >> M >> P >> Y; vector graph(N, vector

()); while(M--) { int A, B, C; cin >> A >> B >> C; A--, B--; graph[A].emplace_back(B, C); graph[B].emplace_back(A, C); } priority_queue, greater

> now; vector cost(N, INT_MAX); now.push({0, 0}); while(!now.empty()) { auto [w, n] = now.top(); now.pop(); if(cost[n] <= w) continue; cost[n] = w; for(auto [to, c] : graph[n]) { if(cost[to] <= w + c) continue; now.push({w + c, to}); } } while(P--) { int D, E; cin >> D >> E; ans = max(ans, (Y - cost[D-1]) / E); } cout << ans << endl; }