철도 연결

시간 제한1초메모리 제한1024 MB

요약

도시별 승객 흐름과 이미 지어진 철도가 주어질 때, 두 도시를 잇는 비용이 두 흐름의 곱인 완전 연결의 최소 비용을 구한다.

문제

비트란디아에서 철도 인프라를 재정비하고 있습니다. 이 작업은 비트란디아 철도 회사의 책임자 마르티나스에게 맡겨졌습니다.

먼저 마르티나스는 각 도시 $i$ 로 들어오는 승객 유입량 $S_i$ 를 산정했습니다. 마르티나스는 다음 조건을 만족하도록 도시들 사이에 철도 노선을 설계합니다.

비트란디아의 어떤 도시에서 출발하더라도 철도를 이용해 다른 모든 도시로 이동할 수 있어야 합니다(반드시 직접 연결될 필요는 없습니다).
도시 $i$ 와 $j$ 사이에 철도 노선 하나를 놓는 비용은 $S_i \times S_j$ 비테우로입니다. 유입량이 클수록 더 큰 역과 더 넓은 주차장 등 더 많은 투자가 필요하기 때문입니다.

비트란디아에는 이미 일부 철도가 놓여 있지만, 예산이 줄어든 마르티나스는 남은 노선을 최소 비용으로 놓으려 합니다.

마르티나스가 제시한 조건을 모두 만족하도록 남은 철도 노선을 놓는 데 드는 최소 비용을 구하세요.

첫째 줄에 공백으로 구분된 두 정수 $N$ 과 $M$ 이 주어집니다. 각각 비트란디아의 도시 수와 이미 놓인 철도 노선 수입니다.

둘째 줄에 공백으로 구분된 $N$ 개의 정수 $S_i$ 가 주어집니다.

이어지는 $M$ 개의 줄에는 각각 두 정수 $v_i$ 와 $u_i$ 가 주어지며, 도시 $v_i$ 와 $u_i$ 사이에 이미 직접 연결된 철도 노선이 있음을 의미합니다.

남은 철도 노선을 모두 놓는 데 드는 최소 비용(비테우로)을 출력하세요.