전기차

Vytautas는 새로 산 반짝이는 전기차를 타고 친구 Vytis를 만나러 가려고 합니다. 두 사람은 모두 Bitland에 사는데, 이 나라는 $1$번부터 $N$번까지 번호가 매겨진 $N$개의 도시로 이루어져 있습니다. Vytautas는 $1$번 도시에, Vytis는 $N$번 도시에 삽니다. 도시들은 양방향으로 통행할 수 있는 $M$개의 도로로 연결되어 있습니다.

가는 길에 Vytautas는 전기차를 충전하기 위해 멈춰야 할 수도 있습니다. $i$번 도시에 충전소가 있다면, 그곳에서는 시간당 $c_i$ kWh를 충전할 수 있습니다. Vytautas는 시간 계획을 세우기 쉽도록 항상 정수 시간 단위로만 충전합니다. 배터리 용량은 $K$ kWh이며, 충전량이 $K$를 넘지는 않습니다. 한 시간이 끝나기 전에 배터리가 가득 차면, Vytautas는 그 시간이 끝날 때까지 차를 충전기에 그대로 연결해 둡니다.

도로 하나를 지나는 데에는 정확히 $1$시간이 걸리고 $L$ kWh를 소모합니다. 차가 새 것이라 출발할 때 배터리는 비어 있습니다.

모든 충전이 정수 시간 동안 이루어져야 한다고 할 때, Vytautas가 $1$번 도시에서 $N$번 도시까지 가는 데 걸리는 최소 시간은 얼마입니까?

첫째 줄에 네 정수가 주어집니다.

• $N$ — 도시의 수;
• $M$ — 도로의 수;
• $K$ — 전기차 배터리의 용량;
• $L$ — 전기차가 도로 하나를 지날 때(한 시간에) 소모하는 전력량.

둘째 줄에 $N$개의 정수 $c_i$ ($0 \le c_i \le K$)가 주어집니다. $i$번 도시에서는 시간당 $c_i$ kWh를 충전할 수 있습니다(만약 $c_i = 0$이면 그 도시에는 충전소가 없습니다).

이어지는 $M$개의 줄에는 각 도로의 양 끝 도시 $a_i$와 $b_i$ ($1 \le a_i, b_i \le N$)가 주어집니다.

$1$번 도시에서 $N$번 도시까지 가는 데 걸리는 최소 시간을 정수 하나로 출력합니다. 그러한 이동이 불가능하면 $-1$을 출력합니다.

• $2 \le N \le 100,000$
• $1 \le M \le 100,000$
• $1 \le K, L \le 100$
• $a_i \ne b_i$
• 두 도시 사이를 직접 잇는 도로는 최대 한 개입니다.