Olet saanut käsiisi JOI Corp. -yhtiön julkaiseman videopelin. Se on hyvin tehty peli, ja olet pelannut sitä joka päivä viihtyen sen parissa.

Eräänä päivänä pelaajien keskuudessa nousi esiin kenttä nimeltä "Laser". Tämä kenttä vaikuttaa äärimmäisen vaikealta, ja sanotaan, että jopa huippupelaajat pääsevät sen läpi vain hyvin pienellä todennäköisyydellä. Yritettyäsi kenttää monta kertaa huomasit, että sen läpäiseminen on mahdollista tekemällä erittäin nopeita ratkaisuja, ja ajattelit, että voisit selviytyä siitä laatimalla ohjelman.

Laserkenttä sijoittuu paikkaan, johon on asetettu $N$ seinää. Kenttä on suorakulmainen ja jaettu $1 \times 1$ -kokoisiin neliöruutuihin. Jokaista ruutua merkitään $(x, y)$ käyttäen kokonaislukuja $x, y \ge 0$. $(0, 0)$ on vasemmassa alakulmassa oleva ruutu, ja $(x, y)$ tarkoittaa ruutua, joka on $x$ ruutua oikealle ja $y$ ruutua ylös ruudusta $(0, 0)$.

Kun kenttä alkaa, viholliset ilmestyvät ja hyökkäävät. Hyökkäyksiä suoritetaan peräkkäin $M$ kappaletta. $j$-nnessä hyökkäyksessä vihollinen ampuu lasersäteen suoraan ruudusta $(P_j, N+1)$ kohti ruutua $(P_j, 0)$.

Jokainen seinä sijaitsee useassa peräkkäisessä ruudussa, joilla on sama $y$-koordinaatti. Seinä $i$ ($1 \le i \le N$) on suorakulmio, jonka vaakasuora leveys on $B_i - A_i + 1$ ja pystysuora korkeus on $1$. Kentän alussa se peittää ruudut $(A_i, i)$ – $(B_i, i)$. Voit siirtää seiniä vaakasuunnassa niin monta kertaa kuin haluat sekä ennen vihollisen ensimmäistä hyökkäystä että minkä tahansa kahden hyökkäyksen välissä. Yhdellä siirrolla voit siirtää yhtä seinää yhden ruudun oikealle tai yhden ruudun vasemmalle.

Kun laser osuu seinään, sen teho heikkenee. Haluat minimoida laserin tehon siirtämällä seiniä niin, että laser osuu kaikkiin seiniin.

Tässä kentässä haluat minimoida seinien siirtojen kokonaismäärän.

Tehtävä

Kun seinien alkusijainnit ja vihollisen hyökkäysten sijainnit on annettu, laske pienin mahdollinen siirtojen määrä kullekin seinälle, jotta jokainen laser osuu jokaiseen seinään.

Syöte

Lue vakiosyötteestä seuraavat tiedot:

• Ensimmäinen rivi sisältää kaksi välilyönnillä erotettua kokonaislukua $N$ ja $M$. Tämä ilmaisee, että tässä kentässä on $N$ seinää ja siinä suoritetaan $M$ hyökkäystä.
• Seuraavien $N$ rivin $i$-s rivi ($1 \le i \le N$) sisältää kaksi välilyönnillä erotettua kokonaislukua $A_i$ ja $B_i$. Tämä ilmaisee, että kentän alussa seinä $i$ on sijoitettu ruudusta $(A_i, i)$ ruutuun $(B_i, i)$.
• Seuraavien $M$ rivin $j$-s rivi ($1 \le j \le M$) sisältää kokonaisluvun $P_j$. Tämä ilmaisee, että $j$-nnessä hyökkäyksessä vihollinen ampuu laserin suoraan ruudusta $(P_j, N+1)$ kohti ruutua $(P_j, 0)$.

Tuloste

Tulosta vakiotulosteeseen $N$ riviä. $i$-nnellä rivillä ($1 \le i \le N$) tulee olla seinän $i$ pienin mahdollinen siirtojen lukumäärä.

Rajoitukset

Kaikki syötetiedot täyttävät seuraavat ehdot:

• $1 \le N \le 200\,000$.
• $1 \le M \le 200\,000$.
• $0 \le A_i \le B_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $0 \le P_j \le 1\,000\,000\,000$ ($1 \le j \le M$).

Osatehtävät

Osatehtävä 1 [10 pistettä]

• $N = 1$ pätee.

Osatehtävä 2 [45 pistettä]

• $A_i = 0$ ($1 \le i \le N$) pätee.

Osatehtävä 3 [45 pistettä]

• Ei lisärajoituksia.

Esimerkit

Syöte 1

4 4
0 3
4 4
2 7
8 11
6
4
3
8

Tuloste 1

5
10
1
7

Huomautus

Tässä syötteessä eräs tapa minimoida seinien siirtojen lukumäärä on seuraava:

• Ennen 1. hyökkäystä: siirrä seinää 1 oikealle 3 kertaa, siirrä seinää 2 oikealle 2 kertaa, älä siirrä seinää 3 ja siirrä seinää 4 vasemmalle 2 kertaa.
• Ennen 2. hyökkäystä: älä siirrä seinää 1, siirrä seinää 2 vasemmalle 2 kertaa, älä siirrä seinää 3 ja siirrä seinää 4 vasemmalle 2 kertaa.
• Ennen 3. hyökkäystä: älä siirrä seinää 1, siirrä seinää 2 vasemmalle 1 kerran, älä siirrä seinää 3 ja siirrä seinää 4 vasemmalle 1 kerran.
• Ennen 4. hyökkäystä: siirrä seinää 1 oikealle 2 kertaa, siirrä seinää 2 oikealle 5 kertaa, siirrä seinää 3 oikealle 1 kerran ja siirrä seinää 4 oikealle 2 kertaa.

Tällä tavoin seinää 1 siirretään 5 kertaa, seinää 2 siirretään 10 kertaa, seinää 3 siirretään 1 kerran ja seinää 4 siirretään 7 kertaa.

Kentän alku

1. hyökkäys

2. hyökkäys

3. hyökkäys

4. hyökkäys

Syöte 2

7 11
12 39
22 23
5 38
6 47
10 43
0 50
18 46
38
19
15
1
12
29
29
0
6
40
6

Tuloste 2

34
178
13
6
18
0
36