4. Taký neporiadok!

V KSP-áckej miestnosti T2 vládol neporiadok – CD-čka sa váľali na zemi, na stole boli porozhadzované vláčiky a koľajnice, a pôvodne svetlomodrý koberec nadobúdal kvôli prachu tmavomodrú farbu.

Všetko sa ale zmenilo od momentu, kedy sa obyvateľom T2 stal Kubo. Ten odmietal znížiť svoje štandardy na životné prostredie, a pustil sa do upratovania.

Pritom si uvedomil, ako veľmi ho upratovanie baví, a tak sa rozhodol, že niekedy uprace aj celú chodbu, na ktorej sa nachádza T2. Zaujíma ho, ako dlho mu to bude trvať – možno to stíha spraviť do začiatku vyučovacej hodiny.

Úloha

Chodbu si vieme predstaviť ako vodorovnú priamku, a miesta na chodbe ako body na tejto priamke. Ich pozície sú na celých číslach \(x\)-ovej osi.

Na niektorých miestach sa nachádzajú smeti, a na niektorých miestach zase smetné koše. Kubo začína v miestnosti T2, a jeho úlohou je presunúť každý odpadok do koša.

V jednej minúte sa vie presunúť medzi dvoma susednými miestami. Ak sa Kubo nachádza na mieste s odpadkom, môže ho zdvihnúť. Toto ho čas nestojí, vie ale držať iba jeden odpadok naraz. Ak sa Kubo nachádza na mieste so smetným košom, vie doň hodiť odpadok, ktorý práve drží. Toto ho tiež nestojí čas. Do každého smetného koša sa zmestí ľubovoľne veľa odpadkov.

Formát vstupu

Na prvom riadku vstupu sa nachádza celé číslo \(t\) – počet testov.

Každý test popisuje jednu situáciu. Popis testu začína prázdnym riadkom.

Na druhom riadku testu sa nachádzajú dve celé čísla \(n, s\) – celkový počet smetných košov aj odpadkov, a začiatočná pozícia Kuba.

Každý z nasledujúcich \(n\) riadkov obsahuje dve celé čísla \(o, p\) – typ objektu, a jeho pozícia na \(x\)-ovej osi. Ak \(o = 0\), tak je to smetný kôš, v opačnom prípade \(o = 1\) a je to odpadok. Pozície jednotlivých objektov tvoria neklesajúcu postupnosť.

Všetky pozície (Kuba aj objektov) sú v absolútnej hodnote najviac \(10^9\).

Obmedzenia

Je \(10\) testovacích sád. Pre jednotlivé sady platia nasledovné obmedzenia.

Formát výstupu

Na jediný riadok výstupu vypíšte jedno celé číslo – najkratší čas, za ktorý vie Kubo presunúť každý odpadok do niektorého smetného koša. Ak Kubo nevie presunúť všetký odpadky do smetných košov, vypíšte namiesto toho \(-1\).

Príklady

Input:

2

5 4
1 -5
1 -3
0 0
1 2
1 3

9 -5
0 -4
1 -1
1 1
1 1
0 2
1 3
0 4
1 7
1 10

Output:

24
31