Johtaja K rakastaa ennustamista ja tekee usein erilaisia ennustuksia. Tänään hän päätti ennustaa Japanin joukkueen menestystä tämän vuoden IOI-kilpailussa käyttäen kortteja, joiden etupuolella on 'I' ja kääntöpuolella 'O'.

Ennustusmenetelmä on seuraava:

1. Päätä ensin positiiviset kokonaisluvut $A, B, C, D, E$.
2. Aseta $A + B + C + D + E$ korttia yhteen riviin. Aseta tällöin $A$ korttia kuvapuoli ylöspäin, niiden perään $B$ korttia kuvapuoli alaspäin, niiden perään $C$ korttia kuvapuoli ylöspäin, niiden perään $D$ korttia kuvapuoli alaspäin ja lopuksi $E$ korttia kuvapuoli ylöspäin. Kun kortit asetetaan tällä tavoin, muodostuu vasemmalta oikealle jono, jossa on $A$ kappaletta 'I'-kirjaimia, $B$ kappaletta 'O'-kirjaimia, $C$ kappaletta 'I'-kirjaimia, $D$ kappaletta 'O'-kirjaimia ja $E$ kappaletta 'I'-kirjaimia.
3. Valitse yksi tai useampi operaatio $N$ ennalta määrätystä tyypistä ja suorita ne missä tahansa järjestyksessä. Voit suorittaa saman tyyppisen operaation kaksi kertaa tai useammin. $i$-nnen tyyppinen operaatio ($1 \le i \le N$) on "käännä kaikki kortit vasemmalta lukien $L_i$-nnestä kortista $R_i$-nteen korttiin". Yhden kortin kääntäminen vie 1 sekunnin. Näin ollen $i$-nnen operaation suorittaminen vie $R_i - L_i + 1$ sekuntia.
4. Kun operaatiot on suoritettu, ennustus onnistuu, jos kaikki kortit ovat kuvapuoli ylöspäin.

Välttääkseen korttien kääntämistä tarpeettomasti johtaja K päätti selvittää ennen korttien varsinaista käyttämistä, onko ennustuksen onnistuminen mahdollista. Lisäksi, jos ennustuksen onnistuminen on mahdollista, hän päätti selvittää siihen tarvittavan vähimmäisajan.

Tehtävä

Kun annetaan tiedot korttien järjestyksestä ja ennalta määrätyistä operaatioista, kirjoita ohjelma, joka selvittää, onko ennustuksen onnistuminen mahdollista, ja jos on, etsii pienimmän ajan, joka tarvitaan sen onnistumiseen.

Syöte

Lue seuraavat tiedot vakiosyötteestä:

• Ensimmäinen rivi sisältää kokonaisluvut $A, B, C, D, E$ välilyönnein erotettuina. Tämä tarkoittaa, että ennustuksen alussa $A$ korttia on kuvapuoli ylöspäin, niiden perässä $B$ korttia kuvapuoli alaspäin, niiden perässä $C$ korttia kuvapuoli ylöspäin, niiden perässä $D$ korttia kuvapuoli alaspäin ja $E$ korttia kuvapuoli ylöspäin.
• Toinen rivi sisältää kokonaisluvun $N$, joka ilmaisee, että ennalta määrättyjä operaatiotyyppejä on $N$ kappaletta.
• Seuraavien $N$ rivin $i$-s rivi ($1 \le i \le N$) sisältää kokonaisluvut $L_i, R_i$ välilyönnein erotettuina. Tämä tarkoittaa, että $i$-s operaatio on "käännä kaikki kortit vasemmalta lukien $L_i$-nnestä kortista $R_i$-nteen korttiin".

Tuloste

Jos ennustuksen onnistuminen on mahdollista, tulosta sen onnistumiseen tarvittava vähimmäisaika kokonaislukuna yhdelle riville. Muussa tapauksessa tulosta -1.

Rajoitukset

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

• $1 \le A \le 100\,000$.
• $1 \le B \le 100\,000$.
• $1 \le C \le 100\,000$.
• $1 \le D \le 100\,000$.
• $1 \le E \le 100\,000$.
• $1 \le N \le 100\,000$.
• $1 \le L_i \le R_i \le A + B + C + D + E$ ($1 \le i \le N$).

Osatehtävät

Osatehtävä 1 [15 pistettä]

• Ehto $N \le 10$ täyttyy.

Osatehtävä 2 [50 pistettä]

• Seuraavat ehdot täyttyvät:
  • $1 \le A \le 50$.
  • $1 \le B \le 50$.
  • $1 \le C \le 50$.
  • $1 \le D \le 50$.
  • $1 \le E \le 50$.

Osatehtävä 3 [35 pistettä]

• Ei ole muita rajoituksia.

Esimerkit

Syöte 1

1 2 3 4 5
3
2 3
2 6
4 10

Tuloste 1

12

Huomautus 1

Aluksi kortit ovat järjestyksessä IOOIIIOOOOIIIII. 2. operaation suorittaminen johtaa tilanteeseen IIIOOOOOOOIIIII. Tämä operaatio vie 5 sekuntia. Tämän jälkeen 3. operaation suorittaminen johtaa tilanteeseen IIIIIIIIIIIIIII, ja ennustus onnistuu. Tämä operaatio vie 7 sekuntia. Ennustus saadaan onnistumaan 12 sekunnissa. Koska tämä on pienin mahdollinen arvo, tulosta 12.

Syöte 2

1 1 1 1 1
1
1 1

Tuloste 2

-1

Huomautus 2

Tässä syöteesimerkissä ennustusta ei voida saada onnistumaan, joten tulosta -1.