Marathon

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long int ll;

struct edge{
    int v;
    int d;
    ll w;
};

int main()
{
    int n,m,k;
    ll t;
    scanf("%d %d %d %lld",&n,&m,&k,&t);
    vector<edge> adj[n+1];
    for(int i=0;i<m;i++){
        int u,v,d;
        ll w;
        scanf("%d %d %d %lld",&u,&v,&d,&w);
        adj[u].push_back({v,d,w});
        adj[v].push_back({u,d,w});
    }
    vector<pair<ll,int> > shoes;
    for(int i=0;i<k;i++){
        ll str;
        int price;
        scanf("%d %lld",&price,&str);
        shoes.push_back({str,price});
    }
    sort(shoes.begin(),shoes.end());
/*  for(int i=0;i<shoes.size();i++){
        printf("(%lld %d)\n",shoes[i].first,shoes[i].second);
    }*/
    int minstr = 2e9;
    int l = 0 , r = shoes.size() - 1;
    while(l <= r){
        int m = (l+r)/2;
        int strength = shoes[m].first;

        //dijkstra
        ll dist[n+1];for(int i=0;i<=n;i++)dist[i] = 2e18;
        bool visited[n+1];for(int i=0;i<=n;i++)visited[i] = false;
        priority_queue<pair<int,int> ,vector<pair<int,int> >,greater<pair<int,int > > > pq;
        pq.push({0,1});
        dist[1] = 0;
        while(!pq.empty()){
            int u = pq.top().second;
            pq.pop();
            if(visited[u])continue;
            visited[u] = true;
            for(int i=0;i<adj[u].size();i++){
                int v = adj[u][i].v;
                int d = adj[u][i].d;
                ll w = adj[u][i].w;
                if(!visited[v] && dist[u] + w < dist[v] && strength >= d){
                    dist[v] = dist[u] + w;
                    pq.push({dist[v],v});
                }
            }
        }

        if(dist[n] <= t){
            if(strength < minstr){
                minstr = strength;
            }
            r = m - 1;
        }
        else{
            l = m + 1;
        }
    }
    int index = 0;
    int ans = 2e9;
    while(shoes[index].first < minstr && index < k)index++;
    while(index < k){
        if(shoes[index].second < ans)ans = shoes[index].second;
        index++;
    }
    printf("%d",(ans == 2e9 ? -1 : ans));
    return 0;
}