문제
발명왕 명석이는 출장을 계획중이다.
명석이는 발명품들을 팔기 위해 1번 도시에서 출발하여 여러 도시들을 방문하는데,
발명왕 명석이는 끝내주는 발명력으로 도시를 방문할때마다 매번 고정된 금액을 벌 수 있다.
다만 명석이는 출장이 길어질수록 소비가 많아지는 경향이 있다.
(소비금액 = C * 출장시간2)
명석이는 출장을 끝내고 다시 1번도시로 돌아와야 하며 모든 도시를 방문할 필요는 없다.
도시가 N개 주어지고, M개의 도시간 연결 관계, 비용 C가 주어질 때,
최대한 많은 금액을 벌 수 있는 방법을 명석이에게 알려주어 발명왕 명석이를 영업왕 명석이로 만들어주자.
1번 도시로부터 어떤 도시도 방문하지 않는 것이 최적인 경우 답은 0이 될 수 있음에 유의하자.
아래 예제의 경우 최적의 여행경로는 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 1 고 이때, 벌어들인 금액은
10 + 20 + 10 + 20 - 1*62 = 24 이다.
입력
첫 번째 줄에 도시의 수 N, 연결의 수 M, 비용 C가 주어진다. (2<=N<=1000) (1<=M<=2000) (1<=C<=1000)
두 번째 줄에는 각 도시에 방문할 경우 벌 수 있는 금액 mi이 주어진다. (0<=mi<=1000)
그 다음 M개의 줄에 걸쳐 도시간 연결 관계가 공백을 구분으로 a와 b (a ≠ b) 정수 2개로 주어진다.
a번 도시에서 b번 도시로 이동이 가능하다는 의미이며 단방향이다.
출력
출장으로 벌 수 있는 최대 금액을 출력한다.
예제1
입력
3 3 1
0 10 20
1 2
2 3
3 1
출력
24
출처
USACO 2020 January Gold