Problem B
Minecraft Speedrunning

Filmklipp från Harrys Minecraft-speedrunning.

Harry och hans vänner har på sistone börjat spela Minecraft tillsammans, och försöker klara av spelet så snabbt som möjligt.

Nu har Harrys gäng lyckats samla ihop alla resurser de behöver för att nå Strongholden, dit man behöver nå för att spelet ska kunna avslutas.

Positionerna mellan gängets nuvarande position och Strongholdens position kan modelleras på en tallinje, där Harrys gäng just nu befinner sig vid position $0$, och Strongholden är beläget vid position $S$.

I Minecraft finns två världar: Overworld och Nether. Harrys gäng och Strongholden befinner sig i Overworld. Nether kan också modelleras som en tallinje, men alla koordinater är komprimerade med en faktor $8$: en position $x$ i Nether motsvarar positionen $8x$ i Overworld.

Längs tallinjen i Nether finns $N$ förstörda Netherportaler. Portal $i$ ligger vid position $x_i$ i Nether och leder till position $8x_i$ i Overworld. För att kunna använda portal $i$ måste den först repareras, vilket tar $t_i$ sekunder. Notera att portalen behöver repareras oavsett om man går igenom från Overworld till Nether, eller Nether till Overworld.

Harrys gäng kan gå längs tallinjen i Overworld till valfri portalutgång (position $8x_i$) eller direkt till Strongholden vid position $S$. Gånghastigheten är $1$, så det tar lika lång tid att gå som avståndet på tallinjen.

Vad är det minsta antalet sekunder det kan ta för Harrys gäng att nå Strongholden från position $0$ i Overworld?

Indata

Första raden innehåller två heltal $N$ och $S$ ($2 \le N \le 2 \cdot 10^5$), ($1 \le S \le 10^9$), antalet förstörda Netherportaler och positionen för Strongholden i Overworld.

Varje av de följande $N$ raderna innehåller två heltal $x_i$ och $t_i$ ($1 \le x_i \le 10^9$, $8x_i < S$), ($1 \le t_i \le 10^9$), positionen för portal $i$ i Nether och tiden det tar att reparera portalen (i sekunder).

Det är garanterat att $x_i < x_{i+1}$ för alla $1 \le i < N$.

Utdata

Skriv ut ett heltal, det minsta antalet sekunder det kan ta för Harrys gäng att nå Strongholden från position $0$ i Overworld.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempelfall 3

Figure 1: Portaler enligt exempelfall 3.

Vi ser att det snabbaste sättet att nå Strongholden är att gå

• från position $0$ till position $16$ vid portal $2$, (tar $16$ sekunder),

• reparera portal $2$ och gå genom den till position $2$ i Nether (tar $t_2 = 5$ sekunder),

• sedan gå till position $4$ i Nether (tar $2$ sekunder),

• reparera portal $4$ och gå igenom den (tar $t_4 = 5$ sekunder),

• och slutligen gå från position $32$ i Overworld till Strongholden vid position $41$ (tar $9$ sekunder).

Totalt tar detta $16 + 5 + 2 + 5 + 9 = 37$ sekunder, vilket går att visa att detta är det minsta möjliga.

2 100
1 1
10 1

39

2 100
1 60
10 60

100

5 41
1 20
2 5
3 1
4 5
5 20

37