여행 timer 1초 memory 512MB

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

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

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

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

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