Happyland는 (1 부터 N까지 번호가 번호가 붙여진) N개의 마을과 마을들을 연결하는 (1 부터 M까지 번호가 붙여 진) M개의 양방향 도로로 이루어져있다.

1번 마을이 Happyland 의 중심마을이다.

마을의 도로망을 이용하여 1번 마을부터 다른 모든 마을들을 방문할 수 있음이 보장되며, 모든 도로는 유료도로이다.

도로 i의 통행료는 c_i센트이며, 도로의 주인에게 납부하여야 한다.

최근에 K개의 도로들이 새로 건설되었으며 소유주는 억만장자인 Mr. Greedy이다.

Mr. Greedy는 새 도로들의 통행료를 결정하여 (통행료가 서로 다를 필요는 필요는 없다) 내일 발표하여야 한다 .

두 주 후에 Happyland 에서는 대규모 축제가 열릴 예정이다. 많은 참가자들이 중심마을에 모여서 행진을 할 예정이다.

마을 j에서는 p_j명의 참가자들이 중심마을인 1번 마을로 갈 예정이다.

이 사람들은 여행에 필요한 미리 선정된 도로들만을 이용하여 중심마을로 갈 것이며, 그 선정된 도로들은 축제 바로 전날 발표가 될 예정이다.

옛 전통에 따라, 도로 선택은 Happyland에서 가장 부자인 Mr. Greedy가 하게 된다.

또한, 같은 전통에 따라 Mr. Greedy는 선택된 도로의 통행료의 합이 최소가 되도록 도로들을 선택해야 하고,

누구나 마을 j에서 마을 1까지의 도로들을 이용할 수 있어야 있어야 한다.

(그러므로, 통행료가 도로의 가중치라면 선택된 에지들은 “최소비용신장트리”를 구성하게 된다)

만약 그러한 에지들의 집합이 여러 개가 있다면, Mr. Greedy는 그 중 하나를 선택할 선택할 수 있다 .

Mr. Greedy는 그가 건설한 K개의 새로운 도로로부터 얻을 수 있는 수입이 단순히 통행료에만 달려있지 않다는 것을 잘 알고 있다.

통행료 수입은 그 도로를 여행한 사람들이 지불한 통행료의 합이다.

보다 자세히 말하자면, 만약 p명의 사람들이 도로 i를 지나간다면, 도로 i로부터 얻는 수입은 c_i*p 가 된다.

옛날 도로들은 Mr. Greedy의 소유가 아니므로, Mr. Greedy 는 새로 건설한 도로로부터만 통행료를 거둘 수 있다.

Mr. Greedy는 엉큼한 계획을 가지고 있다. 그는 도로 선택을 통해 축제기간 동안 거기서 얻는 통행료 수입을 최대화 하려고 한다.

그는 새로운 도로의 통행료를 정하고 축제 때 그 도로를 선택하는 방식으로,

K개의 새로운 도로로부터 얻는 수익을 최대화하는 방법을 알기 원한다.

참고로, Mr. Greedy는 전통에 따라 통행료의 합을 최소화하는 도로들을 선택해야만 한다.

여러분은 기자이며 그의 계획을 폭로하기를 원한다.

그렇게 하기 위해, 먼저 Mr. Greedy가 그의 엉큼한 계획을 통하여 얼마의 수입을 얻을 수 있는지를 구하는 프로그램을 프로그램을 작성하여야 한다 .

Toll timer 3s memory 256MB

Toll 3s 256MB