[HAOI2014] 走出金字塔
题目描述
在探险的过程中,考古学家 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$。
![](https://cdn.luogu.com.cn/upload/pic/5208.png)
输入输出格式
输入格式
第一行共四个整数,$N,M,K,S$,其中,
- $N$ 表示金字塔的层数;
- $M$ 表示出口数;
- $K$ 表示破壁一面墙的时间;
- $S$ 表示考古学家 Dr. Kong 体能维持分钟数。
第二行有两个整数 $X_a,Y_a$ 表示考古学家 Dr. Kong 所在的位置;
第三行至第 $M+2$ 行,每行有两个整数 $X_i,Y_i$,表示有出口的三角形坐标位置。
输出格式
输出 Dr. Kong 走出金字塔后还剩下的体能时间;若不能,输出 $-1$。
输入输出样例
输入样例 #1
4 2 2 10
2 1
3 5
4 4
输出样例 #1
3
说明
### 数据范围及约定
对于全部数据,$1 \le N \le 10^6$,$0\le M\le 10^4$,$0<K\le 20$,$10\le S\le 10^4$。
所有的数据都是整数,且数据之间有一个空格。