Problem F
Samle rutsjebaner

For at sikre, at LTH også i fremtiden har Sveriges mest attraktive studiemiljø, skal der opføres rutsjebaner på universitetsområdet.

Rutsjebanerne bliver bygget i løbet af $N$ dage, hvor fabrikken vil levere ét sporsegment per dag. Hvert sporsegment er ensrettet og har én indkørsel og én udkørsel. Hver rutsjebane skal bestå af mindst to sporsegmenter.

Rutsjebanerne bliver samlet én ad gangen, således at en rutsjebane skal være afsluttet, inden den næste kan påbegyndes.

Det sporsegment, der leveres den første dag, er startsegmentet for den første rutsjebane. På hver af de følgende dage har du to muligheder:

• Tilføj det nye sporsegment i enden af den aktuelle rutsjebane, således at det nye segments indkørsel er koblet til det forudgående segments udkørsel.

• Afslut den aktuelle rutsjebane ved at forbinde dens første og sidste sporsegment. Brug det nye sporsegment som første segment for den næste rutsjebane. Idet afsluttede rutsjebaner skal bestå af mindst to sporsegmenter, kan dette ikke gøres på den sidste dag eller når den aktuelle rutsjebane kun består af ét sporsegment.

På den sidste dag færdiggøres den sidste rutsjebane ved at sammenføje dens første og sidste sporsegmenter.

Hvert sporsegment har en hastighedsbegrænsning i hver ende: en indgående begrænsning $A$ ved indkørslen og en udgående begrænsning $B$ ved udkørslen. Når en vogn kører fra et segment til det næste, skal den overholde både den udgående hastighedsbegrænsning $B$ af det første segment og den indgående hastighedsbegrænsning $A’$ ved indkørslen af det næste segment. Den resulterende hastighedsbegrænsning ved sammenføjningen er altså $\min \{ B, A’ \} $.

Fordi det er sjovere, når det går stærkt, skal rutsjebanerne samles med henblik på at maksimere summen af alle hastighedsbegrænsninger ved sammenføjningene. Antallet af afsluttede rutsjebaner er uvæsentlig. Du kender alle hastighedsbegrænsninger i forvejen.

Indlæsning

Indlæsningens første linje består af et heltal $N$ ($2 \leq N \leq 100\, 000$), antallet af sporsegmenter. Derpå følger $N$ linjer. På den $i$te linje står heltallene $A_ i$ og $B_ i$, som angiver den indgående og udgående hastighedsbegrænsning på det sporsegment, der leveres på den $i$te dag, hvor $A_ i, B_ i \in \{ 1,\ldots , 10^9\} $.

Udskrift

Skriv et enkelt heltal: den maksimalt mulige sum af hastighedsbegrænsninger ved sammenføjningerne af sporsegmenterne.

Pointsætning

Din løsning vil blive testet på en mængde af testgrupper. For at få point for en testgruppe, skal du løse samtlige test i en gruppe.

Eksempelforklaring

I det første eksempel kan segmentere kun samles til en rutsjebane på én måde, idet hver rutsjebane skal bestå av mindst to sporsegmenter. Summen af hastighedsbegrænsningerne er $\min (5, 2) + \min (7, 6) + \min (3, 1) = 9$.

I den andet eksempel består den optimale konstruktion af $3$ rutsjebaner. Den første påbegyndes dag $1$, den anden dag $5$ (når sporsegmentet $16, 12$ leveres) og den tredje på dag $8$ (når sporsegmentet $7, 14$ leveres).

3
1 5
2 7
6 3

9

9
19 3
16 9
2 1
5 19
16 12
11 1
9 16
7 14
18 18

74