스타 트렉

행성 정부들의 성간 연합인 United Federation of Planets(약칭 UFP)는 n개의 행성으로 이루어져 있다. 모든 행성에는 1부터 n까지 번호가 붙어 있다. UFP의 본부는 1번 행성에 있다. UFP는 행성 1에서 행성 n까지 차례로 연결하는 일직선 성간 항로를 건설했다.

성간 여행을 위해 개발된 우주선은 에너지가 거의 무한하여, 두 행성 사이의 항로를 멈추지 않고 이동할 수 있다. 각 행성에는 고유한 우주선 모델이 있다. 우주선의 성능은 거의 같지만 모델에 따라 속도가 다르다. 우주선의 속력은 1광년을 이동하는 데 걸리는 시간으로 나타낸다. 광년은 천문학적 거리를 나타내는 데 쓰이는 거리 단위이다. 우주선의 속력이 10이면 1광년을 이동하는 데 10시간이 걸린다.

1번 행성에 사는 당신은 행성 n으로 여행하려고 한다. 최대한 빨리 행성 n에 도착하기 위해 도중에 다른 행성에서 우주선을 갈아탈 수 있다. 다만 그런 환승에는 착륙, 이륙, 입국 및 출국 수속 등을 준비하는 추가 시간이 필요하다.

예를 들어 UFP에 다섯 개의 행성이 있고, 인접한 행성 사이의 거리, 우주선의 속력, 행성의 준비 시간이 아래 그림과 같다고 하자.

1번 행성의 우주선으로 5번 행성까지 곧바로 이동하면 165시간(= 3 + 27 × 6)이 걸린다. 2번 행성에서 갈아타면 107시간(= 3 + 5 × 6 + 8 + 22 × 3)이 걸린다. 2번 행성에서 갈아타고 4번 행성에서 다시 갈아타면 130시간(= 3 + 5 × 6 + 8 + 14 × 3 + 15 + 8 × 4)이 걸린다. 가능한 모든 여행 계획을 고려하면 5번 행성에 도착하는 최소 시간은 107시간이다.

UFP의 행성과 우주선 정보가 주어졌을 때, 1번 행성에서 n번 행성까지 가는 최소 시간을 구하는 프로그램을 작성하시오.

프로그램은 표준 입력에서 입력을 읽는다. 입력의 첫 줄에는 UFP의 행성 수 n (3 ≤ n ≤ 100,000)이 주어진다. 행성에는 1부터 n까지 번호가 붙어 있다. 다음 줄에는 n − 1개의 정수가 주어지며, i번째 정수는 행성 i와 행성 i + 1 사이의 거리이다. 모든 거리는 1과 1,000 사이이다. 이어서 n − 1개의 줄이 주어지며, i번째 줄에는 두 정수 p와 s (0 ≤ p ≤ 109, 1 ≤ s ≤ 105)가 주어진다. p는 행성 i의 준비 시간이고 s는 행성 i의 우주선 속력이다.

프로그램은 표준 출력에 출력을 쓴다. 정확히 한 줄을 출력한다. 그 줄에는 행성 1에서 행성 n까지 이동하는 최소 시간을 나타내는 정수를 출력한다.