問題文

$N$ 頂点 $M$ 辺の単純無向グラフがあります。$1 \leq i \leq N$ について頂点 $i$ には整数 $A_i$ が書かれています。$1 \leq i \leq M$ について辺 $i$ は頂点 $U_i$ と $V_i$ を結びます。このグラフ上をヘビが歩きます。

ヘビの位置は頭から順に $k$ 個の頂点の列 $(x_1,\dots ,x_k)$ で表されます。ヘビは以下の条件を常に満たします。

• $1 \leq i \leq k-1$ に対し頂点 $x_i$ と $x_{i+1}$ は辺で結ばれている。
• $\displaystyle \max_{1 \leq i \leq k} A_{x_i} - \min_{1 \leq i \leq k} A_{x_i} \leq X$

このヘビの長さは $k$ です。$x_1,\dots ,x_k$ は相異なる必要はありません。

ヘビは以下のような移動を繰り返します。

• 頭がある頂点 $x_1$ に隣接する頂点 $p$ を一つ選ぶ。
• その後ヘビの長さに応じて次のような移動をする。
  • ヘビの長さが $K$ 未満の時、頭の方から長さが $1$ 伸びる。ヘビの位置は $(p, x_1, \dots , x_{k})$ となる。
  • ヘビの長さが $K$ の時、尾の方から長さが $1$ 縮んだ後に頭の方から長さが $1$ 伸びる。ヘビの位置は $(x_1, \dots , x_{k-1})$ となった後に、$(p, x_1, \dots , x_{k-1})$ となる。

以下の条件を満たす異なる $2$ つの整数 $1 \leq i, j \leq N$ の個数を求めてください。

• 頂点 $i$ にいる長さが $1$ のヘビが、何回かの移動を繰り返すことで、ヘビの頭を頂点 $j$ まで到達させることができる。

制約

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq \min(\frac {N \times (N-1)}{2}, 2 \times 10^5)$
• $1 \leq X \leq 10^9$
• $2 \leq K \leq N$
• $1 \leq U_i, V_i \leq N$
• 与えられるグラフは単純
• $1 \leq A_i \leq 10^9$
• 入力は全て整数

入力

$N\ M\ X \ K$
$A_1\ ... A_N$
$U_1\ V_1$
$\vdots$
$U_M\ V_M$

出力

最後に改行してください。

サンプル

サンプル1

入力

5 4 3 3
7 4 1 3 4
1 2
2 3
3 4
4 5

出力

14

与えられたグラフは下図のようになり、$X = 4$、$K = 3$ です。

• 頂点 $1$ から出発して到達できる頂点は $2$ です。
• 頂点 $2$ から出発して到達できる頂点は $1,3,4,5$ です。
• 頂点 $3$ から出発して到達できる頂点は $2,4,5$ です。
• 頂点 $4$ から出発して到達できる頂点は $2,3,5$ です。
• 頂点 $5$ から出発して到達できる頂点は $2,3,4$ です。

よって求める組の個数は $14$ です。

5 4 3 2
7 4 1 3 4
1 2
2 3
3 4
4 5

20