영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
(그림은 원문 저장소에서 볼 수 있습니다)
A video clip from Harry's Minecraft-speedrunning.
Harry and his friends have recently started playing Minecraft together, and are trying to complete the game as fast as possible.
Harry's gang has now managed to gather all the resources they need to reach The Stronghold, the place one needs to reach before the game can end.
The positions between the gang's current position and the Stronghold's position can be modelled on a number line where Harry's gang is currently at position 0, and the Stronghold is located at position S.
In Minecraft, there are two worlds: Overworld and Nether. Harry's gang and the Stronghold exist in the Overworld. The Nether can also be modelled as a number line, but all coordinates are compressed with a factor 8: a position x in the Nether corresponds to the position 8x in the Overworld.
Along the number line in the Nether, there are N destroyed Netherportals. Portal i is located at position x_i in the Nether and leads to the position 8x_i in the Overworld. To be able to use the portal i, it needs to first be repaired, which takes t_i seconds. Note that the portal must be repaired regardless of whether one travels from the Overworld to the Nether or from the Nether to the Overworld.
Harry's gang can walk along the number line in the Overworld to a portal exit of their choice (position 8x_i) or directly to the Stronghold at position S. The walking speed is 1, so it takes as much time to walk as the distance on the number line.
What is the minimum number of seconds it can take for Harry's gang to reach the Stronghold from position 0 in the Overworld?
Input
The first line contains two integers N and S (2 ≤ N ≤ 2 · 10^5), (1 ≤ S ≤ 10^9), the number of destroyed Nether portals and the position for the Stronghold in the Overworld.
Each of the following N lines contain two integers x_i and t_i (1 ≤ x_i ≤ 10^9, 8x_i < S), (1 ≤ t_i ≤ 10^9), the position for portal i in the Nether and the time it takes to repair the portal (in seconds).
It is guaranteed that x_i < x_{i+1} for all 1 ≤ i < N.
Output
Print one integer, the minimum number of seconds it can take for Harry's gang to reach the Stronghold from position 0 in the Overworld.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 15 | N = 2 |
| 2 | 19 | t_i = 1 for all i = 1, …, N. |
| 3 | 27 | N ≤ 1000 |
| 4 | 39 | No additional constraints. |
Explanation of Sample 3
(그림은 원문 저장소에서 볼 수 있습니다)
Figure 1: Portals according to Sample 3.
We see that the fastest way to reach the Stronghold is to go:
- from position 0 to position 16 by portal 2, (takes 16 seconds),
- repair portal 2 and go through it to position 2 in the Nether (takes t_2 = 5 seconds),
- then go to position 4 in the Nether (takes 2 seconds),
- repair portal 4 and go through it (takes t_4 = 5 seconds),
- and finally go from position 32 in the Overworld to the Stronghold by position 41 (takes 9 seconds).
In total, this takes 16 + 5 + 2 + 5 + 9 = 37 seconds, which can be shown to be the least possible amount.
예제
예제 1
2 100 1 1 10 1
39
예제 2
2 100 1 60 10 60
100
예제 3
5 41 1 20 2 5 3 1 4 5 5 20
37