题目描述

小c 同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线，完成打卡任务。

这个游戏的地图可以看作一个包含 $n$ 个结点和 $m$ 条边的有向图，每条边连接两个不同结点，从一个结点到另一个结点之间可能存在多条边。结点编号为从 $1$ 到 $n$ 的连续正整数。

现在有 $T$ 个玩家，每个玩家都有一个体力上限值，均为 $L$。开始时，每个玩家的体力值均为 $0$。每个玩家的打卡任务是跑步：第 $i$ 个玩家的起点为 $s_i$，经费是 $c_i$，任务是跑至少 $d_i$ 的路程。

跑步过程中可以重复经过点和边。

跑步是需要耗费体力的。每跑一条边，会消耗 $1$ 个单位的体力值。如果一个玩家的体力值降为 $0$，该玩家就无法动弹了。为了帮助玩家完成任务，小c 在每个结点处都放置了一种神奇巧克力供玩家选购，食用后可以快速恢复体力。所有结点处的巧克力都是无限量供应的。结点 $i$ 处的巧克力售价为 $p_i$，食用后体力会达到一个指定值 $r_i$；当然，当体力值达到上限后就不会再上升；如果在未食用巧克力前体力值就已经不低于 $r_i$，那么再食用巧克力也不会使体力值上升了。

每天打卡任务开始时，所有玩家从自己的起点出发，沿着边的方向开始跑步，直至完成自己的打卡任务。

每个玩家都希望花最少的费用完成任务。

你能帮助他们设计行程使得各自的花费最少吗？你只需要输出每个玩家完成任务后最多剩余多少钱即可。

输入格式

第一行有四个整数 $n, m, L, T$。

接下来 $n$ 行，每行两个整数 $p_i$ 和 $r_i$。

接下来 $m$ 行，每行三个整数 $u_i, v_i, w_i$，表示从 $u_i$ 到 $v_i$ 有一条长度为 $w_i$ 的有向边。

接下来 $T$ 行，每行三个整数 $s_i, c_i, d_i$。

输出格式

输出 $T$ 行，每行 $1$ 个整数，表示答案。如果某个玩家无法完成打卡任务，则对应行输出 -1

样例输入1

6 6 3 2
4 1
6 2
2 1
8 1
5 4
9 1
1 2 1
1 3 1
2 4 1
3 5 1
4 6 1
5 6 1
1 12 3
1 9 3

样例输出1

2
-1

样例输入2

见附件

样例输出2

见附件

数据范围

$100\% 的数据：2\le n\le 100，1\le m\le 1000，1\le L,T\le 10^5，1\le u_i,v_i,w_i\le n，1\le p_i,r_i\le 10^5，1\le s_i\le n，1\le c_i\le n^2，1\le d_i\le 10^9。$