[HAOI2014]走出金字塔

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file ha14c.in Output file ha14c.out

【题目描述】



在探险的过程中,考古学家Dr. Kong 无意地被困在一个金字塔中。金字塔中的每个房间都是三角形。Dr. Kong可以破壁走到相邻的房间去。例如,如果他目前处于三角形(2,2)房间,那么他可以破壁走到三角形(2,1)、(2,3)或(1,1)房间。但破壁一面墙需要花费K分钟时间,而考古学家Dr. Kong 的体能只能支持他到S分钟。


好在Dr. Kong手中有这个金字塔地图,他发现金字塔有许多出口,一旦他进入一个有出口的三角形房间,他再用1分钟就可以走出金字塔。

现在,你能否帮助Dr. Kong找到一个走出金字塔花费时间最少的出口?若能,输出Dr. Kong走出金字塔后还剩下的体能时间(应当大于或等于0);若不能,输出-1。



【输入格式】


第一行:       N    M   K  S  其中 N表示金字塔的层数;M表示出口数;

                          K表示破壁一面墙的时间;

                          S表示考古学家Dr. Kong体能维持分钟数

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

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


【输出格式】

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

【样例输入】

4 2 2 10
2 1
3 5
4 4

【样例输出】

3

【提示】


【约束条件】

1 <= N <= 1000000     0<=M<=10000    0<K<=20    10<=S<=10000

所有的数据都是整数。数据之间有一个空格


【来源】

在此键入。