어디로 갈까?

$N$개의 정점과 $M$개의 간선으로 이루어진 무방향 그래프가 있다. 이 그래프에는 같은 정점을 잇는 간선이 없고, 두 정점을 잇는 간선은 최대 한 개다.

당신은 임의의 정점에서 출발해 인접한 정점으로 최대 $K$번 이동한다. 이동하지 않는 것도 가능하다. 목표는 얻은 점수의 합을 최대화하는 것이다. 점수는 다음 규칙으로 정해진다.

• 초기 점수는 $0$이다.
• $v$번 정점으로 이동하면 점수 $p_v$를 받는다. $(1 \leq v \leq N)$
• 매 $R$번째 이동마다 $W$점을 추가로 받는다.

점수 합의 최댓값을 구하라.

첫 번째 줄에 다섯 개의 정수 $N$, $M$, $K$, $R$, $W$가 공백으로 구분되어 주어진다. ($2 \leq N \leq 10^6$; $1 \leq M \leq 10^6$; $1 \leq K, R \leq 10^{12}$; $-10^{12} \leq W \leq 10^{12}$)

두 번째 줄부터 $M$개의 줄에 간선 정보가 주어진다. $i$번째 줄에는 $i$번째 간선이 잇는 두 정점 $a_i$와 $b_i$가 공백으로 구분되어 주어진다. ($1 \leq a_i, b_i \leq N$; $a_i \neq b_i$)

그다음 줄에는 $N$개의 정수 $p_1, p_2, \cdots, p_N$이 공백으로 구분되어 주어진다. ($-10^{12} \leq p_j \leq 10^{12}$)

이동 횟수가 $K$를 넘지 않는 어떤 이동 방식을 택하더라도 점수 합의 절댓값이 $2 \times 10^{18}$을 넘지 않는 입력만 주어진다.

점수 합의 최댓값을 출력한다.