32192번 - 어디로 갈까?

문제

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

당신은 어떤 정점에서 출발해서 인접한 정점으로 최대 $K$번 이동할 것이다. 물론, 아예 이동하지 않는 것도 가능하다. 당신의 목표는 점수의 합을 최대화하는 것이다. 점수는 다음 규칙에 따라 주어진다.

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

점수의 합의 최댓값을 계산해 보자!

입력

첫 번째 줄에 5개의 정수 $N,ドル $M,ドル $K,ドル $R,ドル $W$가 공백으로 구분되어 주어진다. $(2\leq N\leq10^6;$ 1ドル\leq M\leq10^6;$ 1ドル\leq K,R\leq10^{12};$ $-10^{12}\leq W\leq10^{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}$을 넘지 않는 입력만이 주어진다.

출력

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

제한

힌트