|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|4 초||512 MB||27||9||5||22.727%|
Nora the kitesurfer is taking part in a race across the Frisian islands, a very long and thin archipelago in the north of the Netherlands. The race takes place on the water and follows a straight line from start to finish. Any islands on the route must be jumped over – it is not allowed to surf around them.
The length of the race is s metres and the archipelago consists of a number of non-intersecting intervals between start and finish line. During the race, Nora can move in two different ways:
While it is not possible to land on or surf across the islands, it is still allowed to visit the end points of any island.
Figure K.1: Illustration of the two sample cases.
Your task is to find the shortest possible time Nora can complete the race in. You may assume that no island is more than d metres long. In other words it is always possible to finish the race.
The input consists of:
The islands do not touch and are given from left to right, that is ri < ℓi+1 for each valid i.
Output one number, the shortest possible time in seconds needed to complete the race. It can be shown that this number is always an integer.
9 3 4 2 2 4 7 8
12 5 3 3 1 3 5 7 8 11