7219번 - Kurjeris 다국어

Artėjant Kalėdoms, Bitlandijos siuntinių kompanija Bitzon turi neįprastai daug darbo.

Bitlandijoje yra N miestų, kuriuos jungia vienas bendras greitkelis. Į Rytus nuo pirmojo miesto įsikūręs kompanijos Bitzon sandėlis. Atstumas nuo Bitzon sandėlio iki pirmojo miesto yra m₁ laiko vienetų, nuo pirmojo iki antrojo miestų – m₂ laiko vienetų, ir taip toliau, kaip pavaizduota iliustracijoje:

Į sandėlį kiekvieną dieną atveža krūvą siuntinių, kuriuos kurjeris turi išvežioti. Kiekvienam siuntiniui nurodytas adresas (miesto numeris) ir laikas, kada siuntinys turi būti pristatytas. Siuntinius kurjeris gali pristatyti anksčiau negu numatyta, bet būtinai ne vėliau nei nurodytu laiku.

Kurjeris išvyksta iš sandėlio ryte (laikysime šį momentą laiku 0), ir važinėja iš vieno miesto į kitą pristatinėdamas siuntinius.

Šiame uždavinyje laikysime, kad siuntinio pristatymas laiko neužima, tiktai važiavimas nuo vieno miesto iki kito.

Žinomas siuntinių sąrašas, kuriuos kurjeris turi pristatyti. Raskite:

1. Ar kurjeris suspės pristatyti visus siuntinius nepavėluodamas.
2. Per kiek mažiausiai laiko kurjeris sugebės pristatyti visus siuntinius ir sugrįžti į sandėlį.

Pirmoje eilutėje įrašytas miestų skaičius N. Antroje eilutėje įrašyta N sveikųjų skaičių – atstumai m₁, m₂, . . . , m_N. Trečioje eilutėje įrašytas siuntinių skaičius K.

Galiausiai seka K eilučių, aprašančių visus siuntinius. Kiekvienoje iš šių eilučių pateikta po du sveikuosius skaičius: miesto numeris a_i (1 ≤ a_i ≤ N), kur siuntinys turi būti pristatytas, ir vėliausias galimas pristatymo laikas t_i.

Laikykite, kad kurjeris išvyksta iš sandėlio laiku 0. Į tą patį miestą gali būti pristatomas daugiau negu vienas siuntinys. Kurjeris siuntinius gali pristatyti bet kuria tvarka (bet nevėluodamas).

Išveskite vienintelį sveiką skaičių – per kiek mažiausiai laiko įmanoma pristatyti visus siuntinius ir sugrįžti į sandėlį. Jeigu bent vieno siuntinio neįmanoma pristatyti laiku – išveskite −1.

• 1 ≤ N ≤ 10 000
• 1 ≤ m_i ≤ 100
• 1 ≤ K ≤ 1000
• 1 ≤ t_i ≤ 1 000 000.