Gara de Nord este cea mai vestită gară din lume. Japonezii, invidioşi pe sistemul performant de întârziere al trenurilor din Gara de Nord, s-au hotărât să analizeze motivul realizării unei astfel de performanţe.
În Gara de Nord (considerată staţia $0$) există $N$ trenuri. Pentru fiecare tren $i$ ştim că va pleca din Gara noastră protagonistă (staţia $0$) şi o să meargă până la staţia $statie{~i~}$ . Staţiile $x$ şi $x+1$ sunt legate în mod direct pentru orice $x$, astfel că trenul $i$ va opri în toate staţiile din intervalul $[0, statie{~i~}]$. De asemenea, ştim că trenul $i$ are o capacitate egală cu numărul maxim de oameni pe care îl poate transporta. Această capacitate este notată cu $capacitate{~i~}$ .
În Gara de Nord (considerată staţia 0) există N trenuri. Pentru fiecare tren i ştim că va pleca din Gara noastră protagonistă (staţia 0) şi o să meargă până la staţia statie i . Staţiile x şi x+1 sunt legate în mod direct pentru orice x, astfel că trenul i va opri în toate staţiile din intervalul[0, statie i ]. De asemenea, ştim că trenul i are o capacitate egală cu numărul maxim de oameni pe care îl poate transporta. Această capacitate este notată cu capacitate i .
Avem $M$ pasageri dornici sa folosească magnificul traseu. Pentru fiecare pasager $i$ ştim intervalul de statii $[a{~i~}, b{~i~}]$ pe care vrea să îl parcurgă. Mai exact, acesta vrea să se urce într-un tren în staţia $a{~i~}$ şi să coboare în staţia $b{~i~}$ .
h2. Cerinta
Din cauza capacităţii limitate a trenurilor, este posibil ca nu toţi pasagerii sa poată obţină un loc şi să ajungă în destinaţia dorită. Să se determine numărul maxim de pasageri care pot ajunge din staţia de plecare în staţia de sosire, precum şi o configuraţie în care aceştia se pot urca în trenuri.
Avem M pasageri dornici sa folosească magnificul traseu. Pentru fiecare pasager i ştim intervalul de statii [a i , b i ] pe care vrea să îl parcurgă. Mai exact, acesta vrea să se urce într-un tren în staţia a i şi să coboare în staţia b i .
h2. Date de intrare
Pe prima linie a fişierului $trenuri3.in$ se află $2$ numere naturale $N$ şi $M$, separate printr-un spaţiu, cu semnificaţia din enunţ. Următoarele $N$ linii vor descrie cele $N$ trenuri. Pe linia $i + 1$ se vor afla două valori întregi separate prin câte un spaţiu: statie $i$ şi capacitate $i$ care descriu trenul cu numărul $i$. Urmatoarele $M$ linii vor descrie itinerariile celor $M$ pasageri. Astfel, pe linia $N + i + 1$ se vor afla două valori întregi $a{~i~}$ şi $b{~i~}$ , separate printr-un spaţiu reprezentând staţiile între care doreşte să circule pasagerul cu numărul $i$.
Fişierul de intrare $trenuri3.in$ ...
h2. Date de ieşire
Pe prima linie a fişierului $trenuri3.out$ se va afişa un număr natural $P$, reprezentând numărul maxim de pasageri care pot să îşi realizeze traseul propus. Pe următoarele M linii se vor afişa M numere naturale. Astfel, pe linia $i + 1$ se va afişa trenul în care va urca pasagerul $i$. Dacă pasagerul $i$ nu poate să se urce în niciun tren, se va afişa valoarea $0$.
În fişierul de ieşire $trenuri3.out$ ...
h2. Restricţii
* $1 ≤ N, M ≤ 100 000$
* $1 ≤ statie{~i~} , capacitate{~i~} ≤ 1 000 000 000$ pentru orice $i, 1 ≤ i ≤ N$.
* $1 ≤ a{~i~} ≤ b{~i~} ≤ 1 000 000 000$ pentru orice $i, 1 ≤ i ≤ M$.
* Un pasager nu poate să coboare dintr-un tren şi să ia alt tren. Pasagerul $i$ poate să urce doar în staţia $a{~i~}$ şi să coboare doar la staţia $b{~i~}$ .
* Pot exista mai multe soluţii pentru repartizarea pasagerilor în trenuri. Orice soluţie cu număr maxim de pasageri posibil va obţine punctaj maxim.
* Pentru afişarea numărului corect de pasageri se va acorda $30%$ din punctajul pe un test.
* Pentru $20%$ din teste $N = 1$.
* Pentru $60%$ din teste $N, M ≤ 2000$.
* Trenurile sunt indexate de la $1$ la $N$.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. trenuri3.in |_. trenuri3.out |
| 2 3
10 1
15 1
2 8
7 10
8 13
| 3
2
1
2
|
| 1 3
10 2
1 5
3 7
4 9
| 2
1
0
1
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
In primul exemplu primul şi ultimul pasager vor urca în trenul $2$, iar pasagerul $2$ în trenul $1$.
Dacă pasagerul $1$ s-ar fi urcat în trenul $1$, ar fi trebuit sa alegem care dintre pasagerul $2$ şi $3$ să se urce în trenul $2$ deoarece cele $2$ itinerarii se intersectează, iar cei doi pasageri nu ar avea loc în acelaşi tren.
In al doilea exemplu orice combinaţie în care selectăm $2$ din cei $3$ pasageri se consideră validă.
...
== include(page="template/taskfooter" task_id="trenuri3") ==
