[HAOI2014]走出金字塔

内存限制：128 MiB 时间限制：10 Sec

在探险的过程中，考古学家Dr. Kong 无意地被困在一个金字塔中。金字塔中的每个房间都是三角形。Dr. Kong可

以破壁走到相邻的房间去。例如，如果他目前处于三角形（2，2）房间，那么他可以破壁走到三角形（2，1）、（

2，3）或（1，1）房间。但破壁一面墙需要花费K分钟时间，而考古学家Dr. Kong 的体能只能支持他到S分钟。好

在Dr. Kong手中有这个金字塔地图，他发现金字塔有许多出口，一旦他进入一个有出口的三角形房间，他再用1分

钟就可以走出金字塔。现在，你能否帮助Dr. Kong找到一个走出金字塔花费时间最少的出口？若能，输出Dr. Kon

g走出金字塔后还剩下的体能时间（应当大于或等于0）；若不能，输出-1。

第一行： N M K S 其中 N表示金字塔的层数；M表示出口数；K表示破壁一面墙的时间；S表示考古学家Dr. Kong体能维持分钟数

第二行: Xa Ya 表示考古学家Dr. Kong所在的位置

第3行~M+2行： Xi Yi 表示有出口的三角形坐标位置

1 <= N <= 1000000 0<=M<=10000 0<K<=20 10<=S<=10000 所有的数据都是整数。数据之间有一个空格

输出Dr. Kong走出金字塔后还剩下的体能时间；若不能，输出-1。

#5169. [HAOI2014]走出金字塔