발명왕 명석이는 출장을 계획중이다.

명석이는 발명품들을 팔기 위해 1번 도시에서 출발하여 여러 도시들을 방문하는데,

발명왕 명석이는 끝내주는 발명력으로 도시를 방문할때마다 매번 고정된 금액을 벌 수 있다.

다만 명석이는 출장이 길어질수록 소비가 많아지는 경향이 있다.

(소비금액 = C * 출장시간²)

명석이는 출장을 끝내고 다시 1번도시로 돌아와야 하며 모든 도시를 방문할 필요는 없다.

도시가 N개 주어지고, M개의 도시간 연결 관계, 비용 C가 주어질 때,

최대한 많은 금액을 벌 수 있는 방법을 명석이에게 알려주어 발명왕 명석이를 영업왕 명석이로 만들어주자.

1번 도시로부터 어떤 도시도 방문하지 않는 것이 최적인 경우 답은 0이 될 수 있음에 유의하자.

아래 예제의 경우 최적의 여행경로는 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 1 고 이때, 벌어들인 금액은

10 + 20 + 10 + 20 - 1*6² = 24 이다.

영업왕 명석이 (Time is Mooney) timer 2초 memory 512MB

영업왕 명석이 (Time is Mooney) 2초 512MB