인간 세상에 이 전령들보다 더 빨리 도착하는 것은 없다.
- 헤로도토스, 『역사』 제8권 98장
당신은 먼 곳으로 명령을 전하고 회신을 받아 돌아와야 하는 전령이다. 말을 바꾸어 타며 쉬지 않고 이동할 수 있도록 길을 따라 역참이 마련되어 있다.
길에는 번부터 번까지 번호가 붙은 개의 역참이 차례로 놓여 있다. 번 역참과 번 역참 사이의 거리는 이다. 당신은 번 역참에서 출발하여 번 역참까지 이동한 뒤 같은 길을 따라 번 역참으로 돌아온다. 이동 순서는 다음과 같으며 다른 이동은 할 수 없다.
첫째 줄에 역참의 수 이 주어진다.
둘째 줄에 구간 거리 이 공백으로 구분되어 주어진다.
왕복 이동에 걸리는 최소 시간을 출력한다.
첫 번째 예제에서는 번 역참의 첫 번째 말을 타고 번 역참으로 이동한 뒤 같은 말을 타고 돌아온다. 왕복 이동에 걸리는 시간은 이다.
각 역참에는 처음에 정확히 두 마리의 말이 있다. 번 역참의 번째 말을 타고 이동하는 데 걸리는 시간은 단위 거리 1당 이다. 따라서 이 말을 타고 거리 를 이동하면 의 시간이 걸린다.
각 구간을 이동할 때에는 출발 역참에 있는 말 한 마리를 골라 탄다. 타고 온 말은 도착 역참에 남는다. 갈 때 탔던 말을 돌아올 때 다시 타는 것도 가능하다.
말에게 휴식을 주기 위해 같은 말을 연속한 두 구간에서 탈 수는 없다. 이 규칙의 유일한 예외는 번 역참에서 돌아오는 경우이다. 번 역참에서는 회신을 준비하는 동안 말도 쉬므로 방금 타고 온 말을 타고 돌아가도 된다.
왕복 이동 시간은 말을 타고 각 구간을 이동하는 데 걸리는 시간의 합으로 계산한다. 처음에 각 역참에 있는 말들의 정보가 주어질 때 왕복 이동에 걸리는 최소 시간을 구하여라.
다음 개의 줄 중 번째 줄에 번 역참에 처음에 있는 두 말의 단위 거리당 이동 시간 과 가 공백으로 구분되어 주어진다.
두 번째 예제에서는 다음과 같이 이동할 수 있다.
총 소요 시간은 이며 이보다 빠르게 왕복할 수 없다.
