Problem F
CCC läger

Det är dags för ett nytt läger i Härryda med Chalmers Coding Club! Per tradition har alla bastat till klockan 3 på morgonen och har nu gått och lagt sig. Hela lägret sover tillsammans i ett stort avlångt rum (Storstugan), men det finns dessvärre också ett fönster längs långsidan riktad rakt mot morgonsolen som snart kommer stiga. Det finns $N$ deltagare där den $i$:te deltagaren sover $d_i$ meter från dörren (på kortsidan) av rummet. Eftersom deltagarna sover i våningssängar, är det möjligt att flera deltagare sover lika långt från dörren.

Illustrering av exempel $1$, med gardiner markerade i rött

Rasmus har vaknat tidigt och märker att det finns ett antal gardiner som täcker delar av fönstret vid $M$ olika ställen. Varje gardin täcker solen för alla som sover mellan $L$ och $R$ (inklusive) meter från dörren, så att de kan sova vidare. Notera att flera gardiner kan täcka solen vid samma del av fönstret. Tyvärr kommer de som inte täcks av en bit gardin träffas av den starka morgonsolen och vakna direkt.

För att hjälpa alla stackars deltagare som kommer att vakna tidigt tänker Rasmus sätta på kaffe. Han tänker att varje deltagare kommer att behöva en kopp kaffe för att vakna ordentligt, men han vet också att Joshua och Gustav var vakna ännu längre för att förbereda morgondagens föreläsningar, så de kommer att behöva två koppar kaffe. Hur många koppar kaffe måste Rasmus sätta på?

Indata

Den Första raden innehåller två heltal $N$ och $M$ ($1 \le N \le 2 \cdot 10^5$, $0 \leq M \leq 2 \cdot 10^5$), antalet medlemmar och antalet bitar gardin.

Detta följs av $N$ rader, den $i$:te raden innehåller namnet på den $i$:te deltagaren följt av $d_i$ ($0 \le d_i \le 10^9$), hur långt från dörren de sover. Varje namn består av 3 till 10 bokstäver. Det börjar med en stor bokstav A-Z, och resten är små bokstäver a-z. Det är garanterat att varje deltagarnamn är unikt.

De följande $M$ raderna innehåller vardera två tal, $L$ och $R$ ($0 \le L_j \le R_j \le 10^9$), vilket betyder att en gardin täcker intervallet $[L, R]$. Notera att vissa gardiner kan överlappa.

Utdata

Skriv ut ett heltal: antalet koppar kaffe som Rasmus måste sätta på för att tillfredställa de nyvakna deltagarna.

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 1

Dessvärre kommer Joshua, Jens och Gustav att vakna. Joshua och Gustav behöver två koppar kaffe vardera, medan Jens endast behöver en. Därmed behöver Rasmus brygga 5 koppar kaffe sammanlagt.

6 2
Jens 0
Loke 1
Joel 3
Joshua 6
Gustav 7
Sebastian 8
1 5
8 8

5

5 2
Julia 3
Joshua 10
Erik 6
Gustav 2
Hugo 13
4 6
1 5

3