== include(page="template/taskheader" task_id="trenuri3") ==

Poveste şi cerinţă...

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 .
 
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