Maraton

#include <bits/stdc++.h>
using namespace std;
using lli=long long;
using pii=pair<lli,lli>;
using pipii=pair<lli,pii>;
vector<pipii> way[100100];
pii shoe[100100];
int n,m,k,t;
bool check(lli num){
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    vector<bool> visited(n+1,false);
    vector<lli> dis(n+1,2e9);
    dis[1]=0;
    pq.push({0,1});
    while(!pq.empty()){
        int u=pq.top().second;
        pq.pop();
        if(visited[u]) continue;
        visited[u];
        for(auto x:way[u]){
            lli w=x.first,v=x.second.first,d=x.second.second;
            if(num>=d&&!visited[v]&&dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                pq.push({dis[v],v});
            }
        }
    }
    if(dis[n]>t) return false;
    return true;
}

int main(){
    scanf("%d%d%d%d",&n,&m,&k,&t);
    for(int i=0;i<m;i++){
        int u,v,d,w;
        scanf("%d%d%d%d",&u,&v,&d,&w);
        way[u].push_back({w,{v,d}});
        way[v].push_back({w,{u,d}});
    }
    for(int i=0;i<k;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        shoe[i]={v,u};
    }
    sort(shoe,shoe+k);
    lli l=0,r=k-1;
    lli mn=2e18;
    while(l<=r){
        lli mid=(l+r)/2;
        if(check(shoe[mid].first)){
            mn=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    lli ans=2e9;
    if(mn==2e18) printf("-1");
    else{
        for(int i=mn;i<k;i++){
            ans=min(ans,shoe[i].second);
        }
        printf("%d",ans);
    }
}