题目描述

$\hspace{15pt}$ hina 误入了小憨的矩阵，这个矩阵的大小是 $n \times m$ ，他使用 $(i,j)$ 来表示矩阵的第 $i$ 行第 $j$ 列。

$\hspace{15pt}$现在 hina 正位于矩阵的 $(1,1)$ 位置，他的目标是到达 $(n,m)$ 位置。每次他可以消耗一点时间向上下左右四个方向之一移动一格。矩阵中某些格子上有传送门，若 hina 处于传送门的位置则可以消耗 $t$ 点时间直接瞬间移动到 $(n, m)$ 位置。当然， hina 也可以选择不使用传送门。

$\hspace{15pt}$ 请你告诉 hina 到达 $(n, m)$ 位置所需的最少时间。

输入格式

$\hspace{15pt}$第一行输入两个正整数 $n,m\,(1\leq n,m \leq 10^9)$ 表示矩阵的大小。

$\hspace{15pt}$第二行输入两个正整数 $k,\,t\,(0 \leq k, t \leq 10^5)$ 分别表示传送门的数量和使用传送门消耗的时间。

$\hspace{15pt}$接下来 $k$ 行，第 $i\,(1 \leq i \leq k)$ 行输入两个整数 $x_i\,(1 \leq x_i \leq n),y_i\,(1 \leq y_i \leq m)$，表示第 $i$ 个传送门在 $(x_i, y_i)$ 格上。

$\hspace{15pt}$输入保证 $(1,1)$ 格和 $(n, m)$ 格不存在传送门且所有传送门互不重叠。

输出格式

$\hspace{15pt}$输出一个正整数，表示 hina 到达 $(n, m)$ 位置所需的最短时间。

测试样例

3 3
1 0
2 2

2

3 3
1 4
2 2

4

1000000000 1000000000
3 0
2 3
3 4
999999999 999999999

3