Županijsko natjecanje iz informatike 2016. / Prva podskupina (1. i 2. razred) - 4. zadatak

Alen je vlasnik, konobar i kuhar u malenom restoranu na Jadranskoj obali.

Svakog jutra Alen prima predbilježbe za obroke – svaki gost odredi vremenski interval u kojemu je voljanzapočeti objed. Radno vrijeme restorana je, za potrebe ovog zadatka, podijeljeno u \(1000000 (\)milijun)minuta označenih prirodnim brojevima od \(1\) do \(1000000\), a interval gosta k je zadan s dva prirodna brojaaki bk– oznakom prve i zadnje minute (uključivo) u kojoj je gost voljan početi objed.

Kako je restoran mali, samo jedan gost može objedovati u pojedinoj minuti, a vrijeme objeda ovisi ovrsti hrane koja se taj dan poslužuje. Svaki dan se poslužuje samo jedna vrsta hrane za koju je trajanjekonzumacije određeno fiksnim prirodnim brojem t. Ako gost započne obrok u minuti x, onda sljedeći gostmože najranije započeti obrok u minuti x+t.

Alen ne mora primiti svakog gosta, ali onaj gost kojeg primi mora započeti obrok unutar odabranogvremenskog intervala. Dozvoljeno je da gost završi s objedom izvan odabranog intervala te čak izvanradnog vremena restorana.

Alen je zaprimio predbilježbe za obroke te pokušava odrediti koju vrstu hrane ponuditi. Zadano je mvrsta hrane čije su trajanja konzumacije redom t\(1\), t\(2\), ..., tm. Za svaku vrstu hrane odredite maksimalnibroj gostiju koje Alen može poslužiti ako je ponudi taj dan.

Ulazni​ podaci

U prvom redu nalazi se prirodni broj n (n\(\leq 18 )\) – broj gostiju. U k-tom od sljedećih n redova nalaze seprirodni brojevi aki bk(ak\(\leq\)bk\(\leq 1000000 )\) – početna i završna minuta vremenskog intervala gosta k.U sljedećem redu nalazi se prirodni broj m (m\(\leq 50 )\) – broj vrsta hrane. U k-tom od sljedećih m redovanalazi se prirodni broj tk(tk\(\leq 1000000 )\) – trajanje konzumacije k-te vrste hrane.

Izlazni podaci

Potrebno je ispisati m redova. U k-ti red ispišite maksimalni broj gostiju koje Alen može poslužiti akopriprema hranu vrste k.

Bodovanje

• U test podacima vrijednim \(30 \%\) bodova vrijedit će n\(\leq 5\) i najveći broj u ulazu će biti manji ilijednak \(1000\).

• U test podacima vrijednim dodatnih \(30 \%\) bodova vrijedit će n\(\leq 10\) i najveći broj u ulazu će bitimanji ili jednak \(1000\).

Primjeri test​ podataka

Ulaz

3
2 5
3 3
5 8
3
2
3
100

Izlaz

3
2
1

Ulaz

3
1 5
595 600
595 600
2
6
5

Izlaz

2
3