루미 알고리즘

#1636골드Minecraft Speedrunning

PO 2026 결선코딩출제 Harry Zhang, Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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.

GroupPointsConstraints
115N = 2
219t_i = 1 for all i = 1, …, N.
327N ≤ 1000
439No 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

출처 표기

출처: Programmeringsolympiaden 2026년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.