n개의 행성으로 이루어진 행성 연합 UFP(United Federation of Planets)가 있다. UFP의 본부는 1번 행성에 있으며, 행성들은 1번부터 n번까지 번호가 매겨져 있다. UFP는 1번 행성부터 n번 행성까지 순서대로 이어지는 일직선 형태의 우주 항로를 구축했다.
행성 간 여행을 위해 개발된 우주선은 에너지가 거의 무한하여, 두 행성 사이를 이동하는 동안 중간에 멈출 필요가 없다. 각 행성에는 그 행성 고유의 우주선 모델이 하나씩 있다. 우주선들의 성능은 거의 비슷하지만, 모델마다 속도가 다르다. 우주선의 속도는 1광년을 이동하는 데 필요한 시간(시간 단위) 으로 나타낸다. 광년은 천문학적 거리를 나타내는 거리 단위이다. 예를 들어 우주선의 속도가 10이라면, 1광년을 이동하는 데 10시간이 걸린다는 뜻이다.
당신은 1번 행성의 주민으로, 이제 n번 행성으로 가려고 한다. 최대한 빨리 도착하기 위해, 이동 도중 다른 행성에서 우주선을 갈아탈 수 있다. 다만 우주선을 갈아타려면 착륙, 이륙, 입출항 절차 등 준비에 추가 시간이 필요하다는 점을 알아야 한다.
예를 들어, UFP에 5개의 행성이 있고, 인접한 행성 사이의 거리, 각 행성 우주선의 속도, 그리고 각 행성의 준비 시간이 아래 그림과 같다고 하자.
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번 행성까지 가는 최소 시간을 구하는 프로그램을 작성하여라.
입력
표준 입력에서 다음과 같이 주어진다.
첫째 줄에 정수 n이 주어진다. (3 ≤ n ≤ 100,000)
둘째 줄에는 n - 1개의 정수가 주어지며, 이 중 i번째 정수는 i번 행성과 i + 1번 행성 사이의 거리를 의미한다. 모든 거리는 1 이상 1,000 이하이다.
이후 n - 1개의 줄에 걸쳐, i번째 줄마다 두 정수 p와 s가 주어진다. (0 ≤ p ≤ 10^9, 1 ≤ s ≤ 10^5) 여기서 p는 i번 행성의 준비 시간, s는 i번 행성 우주선의 속도를 의미한다.
출력
표준 출력에 정확히 한 줄을 출력한다.
그 줄에는 1번 행성에서 n번 행성까지 이동하는 최소 시간을 나타내는 정수 하나를 출력한다.
rlatjwls3333 7달 전
문제
n개의 행성으로 이루어진 행성 연합 UFP(United Federation of Planets)가 있다. UFP의 본부는1번 행성에 있으며, 행성들은1번부터n번까지 번호가 매겨져 있다. UFP는1번 행성부터n번 행성까지 순서대로 이어지는 일직선 형태의 우주 항로를 구축했다.행성 간 여행을 위해 개발된 우주선은 에너지가 거의 무한하여, 두 행성 사이를 이동하는 동안 중간에 멈출 필요가 없다. 각 행성에는 그 행성 고유의 우주선 모델이 하나씩 있다. 우주선들의 성능은 거의 비슷하지만, 모델마다 속도가 다르다. 우주선의 속도는 1광년을 이동하는 데 필요한 시간(시간 단위) 으로 나타낸다. 광년은 천문학적 거리를 나타내는 거리 단위이다. 예를 들어 우주선의 속도가
10이라면,1광년을 이동하는 데10시간이 걸린다는 뜻이다.당신은
1번 행성의 주민으로, 이제n번 행성으로 가려고 한다. 최대한 빨리 도착하기 위해, 이동 도중 다른 행성에서 우주선을 갈아탈 수 있다. 다만 우주선을 갈아타려면 착륙, 이륙, 입출항 절차 등 준비에 추가 시간이 필요하다는 점을 알아야 한다.예를 들어, UFP에
5개의 행성이 있고, 인접한 행성 사이의 거리, 각 행성 우주선의 속도, 그리고 각 행성의 준비 시간이 아래 그림과 같다고 하자.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번 행성까지 가는 최소 시간을 구하는 프로그램을 작성하여라.입력
표준 입력에서 다음과 같이 주어진다.
첫째 줄에 정수
n이 주어진다. (3 ≤ n ≤ 100,000)둘째 줄에는
n - 1개의 정수가 주어지며, 이 중i번째 정수는i번 행성과i + 1번 행성 사이의 거리를 의미한다. 모든 거리는1이상1,000이하이다.이후
n - 1개의 줄에 걸쳐,i번째 줄마다 두 정수p와s가 주어진다. (0 ≤ p ≤ 10^9,1 ≤ s ≤ 10^5) 여기서p는i번 행성의 준비 시간,s는i번 행성 우주선의 속도를 의미한다.출력
표준 출력에 정확히 한 줄을 출력한다.
그 줄에는
1번 행성에서n번 행성까지 이동하는 최소 시간을 나타내는 정수 하나를 출력한다.예제 입력 1
예제 출력 1
예제 입력 2
예제 출력 2