Hamsterul Vlăduţ are nevoie de ajutorul vostru pentru a-şi realiza planul şi vă cere să aflaţi pentru fiecare zi dintre cele <tex>Q</tex> ale dietei sale, care este numărul optim (minim) de plăci pe care trebuie să le folosească pentru a acoperi complet găurile pe care le are de parcurs (o placă nu are voie să acopere o celulă doar parţial, iar o gaură se consideră acoperită dacă se află oriunde în interiorul plăcii, sau pe capete, exact ca la un interval închis).

!hamster?poza.jpg!
 

h2. Date de intrare
Fişierul de intrare $hamster.in$ conţine pe prima linie două numere naturale nenule, separate printr-un spaţiu, ce reprezintă în ordine numerele <tex>N</tex> şi <tex>Q</tex> din enunţ. Pe următoarea linie se găsesc <tex>N</tex> numere naturale nenule separate două câte două alăturate printr-un spaţiu, reprezentând indicii celulelor după care Bobo sapă un şanţ, în ordine crescătoare. Fişierul mai conţine încă <tex>Q</tex> linii, pe linia <tex>2+j</tex> găsindu-se două numere naturale nenule separate printr-un spaţiu, reprezentând în ordine <tex>K_i</tex> şi <tex>D_i</tex>.