#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 103

#define inf 1000000300

#define setIO(s) freopen(s".in","r",stdin)  //, freopen(s".out","w",stdout)

using namespace std;

int n,m,C,T;

int p[N],c[N],dis[N][N][22],go[N][N],tmp[N][N],f[N][N*N];

int main()

{

    int i,j,k;

    // setIO("input");

    scanf("%d%d%d%d",&n,&m,&C,&T);

    memset(dis,0xc2,sizeof dis);

    for(i=1;i<=n;++i) scanf("%d%d",&p[i],&c[i]), dis[i][i][0]=0;

    for(i=1;i<=m;++i)

    {

        int a,b,l;

        scanf("%d%d%d",&a,&b,&l);

        dis[a][b][0]=max(dis[a][b][0], l);

    }

    for(int t=1;t<=20;++t)

    {

        for(i=1;i<=n;++i)

            for(j=1;j<=n;++j)

                for(k=1;k<=n;++k)

                    dis[i][j][t]=max(dis[i][j][t], dis[i][k][t-1]+dis[k][j][t-1]);

    }

    for(i=1;i<=n;++i)

    {

        int cc=min(c[i], C);

        for(j=1;j<=n;++j) go[i][j]=tmp[i][j]=-inf;

        go[i][i]=0;

        for(int l=0;l<=20;++l)

        {

            if((1<<l)&cc)

            {

                for(j=1;j<=n;++j)

                    for(k=1;k<=n;++k)

                        tmp[i][j]=max(tmp[i][j], go[i][k]+dis[k][j][l]);

                for(j=1;j<=n;++j) go[i][j]=tmp[i][j];

            }

        }

    }

    for(i=1;i<=n;++i) f[i][0]=0;

    for(j=1;j<=n*n;++j)

    {

        for(i=1;i<=n;++i)

            if(j>=p[i])

            {

                for(k=1;k<=n;++k)

                    f[i][j]=max(f[i][j], go[i][k]+f[k][j-p[i]]);

            }

    }

    int cas;

    for(cas=1;cas<=T;++cas)

    {

        int s,q,d;

        scanf("%d%d%d",&s,&q,&d);

        int l=1,r=q,mid,ans=-1;

        while(l<=r)

        {

            mid=(l+r)>>1;

            if(f[s][mid]>=d) ans=mid,r=mid-1;

            else l=mid+1;

        }

      //  printf("%d\n",f[s][ans]);

        printf("%d\n",ans==-1?ans:q-ans);

    }

    return 0;

}