DAY几了？
T1：
原本想人类智慧的，忘记了，然后就结束了
观察到波动次数为log级别，暴力即可
T2：
水，不在序列中的数有两种：没加入的或删掉的
没加入的最小值很好维护，删掉的观察到还原顺序为一个队列，直接单调队列维护就好了
T3：
倍增，先考虑dp
类似floyd，又像是背包，状态转移时看做只吃当前位置上的食物能走到的地方（中途不再吃），设dp[i][j]表示用i块，从j开始的最大权值
枚举走到h，易得dp[i][j]=dp[i-p[i]][h]+d[j][h]
d[j][h]表示j走到h的最长路径
求d[j][h],也要枚举中转点，还要枚举走了几步
观察到数据有点大，考虑先倍增跑掉一部分，之后每个点跑时只需要二进制拆分就行了
考虑如何倍增，很明显g[i][j][x]表示从i~j走<=2^x步的最长路径，则g[i][j][x]=g[i][h][x-1]+g[h][j][x-1]取MAX
（注意g[i][i][1]=g[i][i][0]=0,其余都为负无穷，意为走到没路了可以自己转圈，避免走出图）
#include
using namespace std;
long long n,m,C,t,p[100005],c[100005],head[100005],nex[100005],u[100005],v[100005],l[100005],s,q,D,g[105][105][21],L,r,mid;
long long d[105][105],ls[105],f[10005][105];
void work() {
for(long long x=1; x<=n; x++) {
for(long long i=head[x]; i!=0; i=nex[i]) {
g[x][v[i]][0]=max(g[x][v[i]][0],l[i]);
}
g[x][x][0]=0;
}
for(long long i=1; i<=20; i++) {
for(long long x=1; x<=n; x++) {
for(long long j=1; j<=n; j++) {
for(long long h=1; h<=n; h++) {
g[x][j][i]=max(g[x][j][i],g[x][h][i-1]+g[h][j][i-1]);
}
}
}
}
}
void puT()
{
for(long long i=1; i<=n*n; i++) {
cout<<i<<": "<<endl;
for(long long j=1; j<=n; j++) {
cout<<j<<": "<<f[i][j]<<" "<<endl;
}
cout<<endl;
}
}
void run() {
for(long long i=1;i<=n;i++) d[i][i]=0;
for(long long i=0; i<=20; i++) {
for(long long x=1; x<=n; x++) { //起点
if((c[x]&(1<=1) {
for(long long j=1; j<=n; j++) { //终点
ls[j]=-114514191;
for(long long h=1; h<=n; h++) { //中转点
ls[j]=max(ls[j],d[x][h]+g[h][j][i]);
}
}
for(long long j=1; j<=n; j++) d[x][j]=max(d[x][j],ls[j]);
}
}
// if(i==1) puT();
}
}
void roundgod() {
for(long long i=1; i<=n*n; i++) { //花费
for(long long j=1; j=p[j]) {
for(long long h=1; h<=n; h++) { //中转点
f[i][j]=max(f[i][j],d[j][h]+f[i-p[j]][h]);
}
}
}
}
}
int main() {
// memset(f,-0x3f,sizeof(f));
freopen("mario2.in","r",stdin);
freopen("mario.out","w",stdout);
memset(d,-64,sizeof(d));
for(long long i=1; i<=104; i++) for(long long j=1; j<=104; j++) {
d[i][j]=-114514191;
for(long long h=0; h<=20; h++) g[i][j][h]=-114514191;
}
for(long long i=1;i<=10004;i++) for(long long j=1;j<=n;j++) f[i][j]=-114514191;
scanf("%lld%d%d%d",&n,&m,&C,&t);
for(long long i=1; i<=n; i++) scanf("%lld%d",&p[i],&c[i]);
for(long long i=1; i<=m; i++) {
scanf("%lld%d%d",&u[i],&v[i],&l[i]);
nex[i]=head[u[i]];
head[u[i]]=i;
}
work();//倍增求最长路
run();//求d[i][j]
roundgod();//求f[q][i]
// puT();
for(long long i=1; i<=n*n; i++) {
for(long long j=1; j<=n; j++) {
f[i][j]=max(f[i][j],f[i-1][j]);
}
}
for(long long j=1; j<=n; j++) f[n*n+1][j]=114514191;
while(t--) {
//cout<<"-1"<<endl;
scanf("%lld%d%d",&s,&q,&D);//起点，钱，目标里程
L=0,r=n*n+1;
while(L=D) r=mid;
else L=mid+1;
}
if(L>q) printf("-1\n");
else printf("%lld\n",q-L);
// if(q-L==100){
// printf("- %lld %lld\n",f[0][s],D);
// }
}
return 0;
}