한컴이는 정올국으로 여행을 떠났다.

정올국은 N개의 도시를 N-1개의 도로가 연결하는 형태이며, 어느 두 임의의 도시도 도로만을 사용해 이동할 수 있다.

한컴이는 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시를 순서대로 이동한 다음 N번 도시에서 비행기를 타고 귀국할 예정이다. 이때 이동하는 도중 중간에 다른 도시에 도착해도 목적지가 아니라면 무시하고 계속 움직일 것이다.

정올국의 각 도로는 두 가지의 요금제가 있다. 첫 번째는 한번 도로를 사용할 때마다 C_{i1}원씩 청구되는 형태이고, 두 번째는 C_{i2}원을 청구한 뒤 차후 무제한으로 도로를 사용하는 형태이다.

한컴이의 여행에 필요한 요금의 최소값을 구하시오.

여행 timer 1초 memory 512MB

여행 1초 512MB