景区旅行

题目描述

$A$市具有$n$个景点和$m$条道路，所有景点编号为$1$,$2$,$\ldots$,$n$。道路是有向且具有一个长度，连接景点中的某两个。

每个景点都有一个加油站。第$i$个景点的加油站编号也为$i$，且具有如下性质：

• 若汽车在第$i$个加油站加油，则需要花费$v_{i}$元钱。
• 若汽车在第$i$个加油站加油，则车的油量将被加至油量上限与$x_{i}$中的较小值。不过如果加油前汽车油量已经不小于$x_{i}$，则不能在该景点加油。

你准备来到$A$市旅游。你的汽车的油量上限为$X$。旅游开始时，汽车没有油。在旅游过程中：

1. 如果汽车有油（不为$0$），汽车可以花费$1$的汽油从当前景点选择一条道路到达另一个相邻的景点；
2. 当汽车在景点$i$且当前油量小于$x_{i}$时，汽车可以在这个景点的加油站加油。加油需花费$v_{i}$元钱，这样汽车油量将被加到$\min(X,x_{i})$。

一次旅游花的钱为所有加油花费的钱之和。一次旅游经过的总路程为所有开车走过的道路的长度的和。可以在一个加油站多次加油，也可以多次走过同一条路，费用和路程都要相应地累加进总和中。

你计划旅游$T$次，每次旅游前，你都指定了这次旅游从哪里出发，至少应该开车经过多远的路程。由于你的经济状况不同，每次出发前带上的钱也不同。为了省钱，你需要在旅游前先规划好旅游经过的道路和在哪些加油站进行加油，使得从起点出发，按照该路线旅游结束后经过的路程不少于你定下的目标，且花的钱尽可能少。请你提前计算出这$T$次旅游每次结束后最多可以剩下多少钱。

输入格式

输入第一行包含四个正整数$n$，$m$，$C$，$T$，每两个整数之间用一个空格隔开，分别表示景点数、道路数、汽车油量上限和旅行次数。

接下来$n$行，每行包含两个正整数$v_{i}$，$x_{i}$，每两个整数之间用一个空格隔开，按编号顺序依次表示编号为$1$,$2$,$3$,$\ldots$,$n$的景点的费用和油量。

接下来$m$行，每行包含三个正整数$a_{i}$，$b_{i}$，$l_{i}$，每两个整数之间用一个空格隔开，表示一条从编号为$a_{i}$的景点到编号为$b_{i}$的景点的道路，道路的长度为$l_{i}$。保证$a_{i} \neq b_{i}$，但从一个景点到另一个景点可能有多条道路。

最后$T$行，每行包含三个正整数$s_{i}$，$q_{i}$，$d_{i}$，描述一次旅游计划，旅游的起点为编号为$s_{i}$的景点，出发时带了$q_{i}$元钱，目标路程为$d_{i}$。

输出格式

输出$T$行，每行一个整数，第$i$行的整数表示第$i$次旅游结束后最多剩下多少元钱。如果旅游无法完成，也就是说不存在从景点$s_{i}$出发用不超过$q_{i}$元钱经过不小于$d_{i}$的路程的路线，则该行输出$-1$。

数据范围与提示

其中，特殊性质如下：

• 特殊性质$1$：所有$a_{i}=i$，$b_{i}=i+1$，$l_{i}=1$。
• 特殊性质$2$：所有$d_{i} \leq 10^{3}$。
• 特殊性质$3$：所有$q_{i} \leq 100$。

对于$100\%$的测试点，保证$2 \leq n \leq 100$，$1 \leq m \leq 1000$，$1 \leq C$，$T \leq 10^{5}$，$1 \leq a_{i}$，$b_{i}$，$l_{i} \leq n$，$1 \leq v_{i}$，$x_{i} \leq 10^{5}$，$1 \leq s_{i} \leq n$，$1 \leq q_{i} \leq n^{2}$，$1 \leq d_{i} \leq 10^{9}$。

样例

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

2
-1

说明

$T$城的景区和道路如下图所示：

第$1$次旅游，最优路线为先在景点$1$加油，花费$4$元，此时油量为$1$，然后到景点$2$，此时油量为$0$，在景点$2$加油，花费$6$元，此时油量为$2$，接着到景点$4$，此时油量为$1$，最后到景点$6$，总路程为$3$，最后剩余$12-4-6=2$元。

第$2$次旅游，只用$9$元无论如何也无法走$3$的路程，因此旅游无法完成。

见trip2.in 

见trip2.ans