A — Fincsi bubis tea

A bubis tea (bubble tea) manapság az egyik legnépszerűbb ital Vietnamban. Az utcákon sétálva mindenfelé bubis tea üzletekbe botlunk. Számos bubis tea márka létezik már: Bobapop, Chago, DingTea, GongCha, Mr.GoodTea, RoyalTea, ToCoToCo… A bubis tea nemcsak a finom íze miatt vonzza a hallgatókat, hanem a különböző extra ízesítések nagy választéka miatt is: aloe vera, csokilapka, kókuszzselé, tojáspuding, gyümölcsgyöngyök… Na most már abbahagyom ezt a felsorolást, mert úgy érzem, azonnal szereznem kell egy kis bubis teát. Annyira, de annyira addiktív!

Bubis tea

Ízesítések

Miután PVH megtartotta a Nemzetközi Filozófiai Olimpiára történő felkészítő óráját a vietnami hallgatóknak, meghívja őket egy csésze bubis teára. A teaüzlet N-féle teát és M-féle ízesítést árul. Minden teafajtának és ízesítésnek ismerjük az árát. PVH minden hallgatónak vesz egy csésze teát pontosan egyféle ízesítéssel. Egy csésze ára a tea árának és az ízesítés árának az összege. Azonban nem minden ízesítés keverhető mindegyik teával. Minden teafajtához ismerjük azoknak az ízesítéseknek a listáját, amelyekkel keverhető.

Ha tudjuk, hogy mennyi pénze van PVH-nak, határozzuk meg, hány hallgatót tud meghívni, ha egy hallgató pontosan egy bubis teát iszik! Ne feledjük, hogy PVH sosem nézi csak úgy, hogy a hallgatói bubis teát isznak, anélkül hogy maga is inna, tehát először is magának kell vásárolnia egyet!

A bemenet specifikációja

Az első sorban egyetlen egész szám (N) szerepel, amely a teaüzletben kapható teaféleségek számát adja meg.

A második sor N egész számot tartalmaz: az egyes teafajták árait.

A harmadik sorban egyetlen egész szám (M) szerepel, amely a teaüzletben kapható ízesítések számát adja meg.

A negyedik sor M egész számot tartalmaz: az egyes ízesítések árait.

A következő N sor közül az i-edik azokat az ízesítéseket adja meg, amelyek keverhetők az i-edik fajta teával. A sor egy K egész számmal kezdődik, ezt K egész szám követi, amelyek az [1, M] tartományba esnek és páronként különbözőek. Mindegyik szám egy olyan ízesítést jelöl, amely keverhető az i-edik fajta teával.

Az utolsó sorban egy X egész szám szerepel, amely a PVH-nál lévő pénz mennyiségét adja meg.

A kimenet specifikációja

A kimenetre egyetlen sort kell kiírni, amely azoknak a hallgatóknak a maximális számát tartalmazza, akiknek PVH tud venni bubis teát.

Korlátozások

A pénzösszeg 1 és 10⁹, a bemeneten szereplő összes többi szám pedig 1 és 1000 közé esik.

Példa bemenet

1. 3
2. 10 20 30
3. 5
4. 1 2 3 4 5
5. 2 4 5
6. 3 1 2 3
7. 5 1 2 3 4 5
8. 42

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. 2

letöltés szöveges állományként

A példa magyarázata

A példában háromféle tea szerepel, amelyeknek az árai 10, 20 és 30. Adva van továbbá ötféle ízesítés, amelyek az árai rendre 1, 2, 3, 4 és 5.

A legolcsóbb tea-ízesítés kombináció az első tea a negyedik ízesítéssel, amelynek a költsége 14. Megjegyezzük, hogy az első tea az első ízesítéssel alacsonyabb árú kombinációt adna (11), de ez nem megengedett, mivel az első tea csak a negyedik és ötödik ízesítéssel kombinálható (lásd a bemenet ötödik sorát).

Így tehát 42 egység pénzből PVH három csésze teát tud vásárolni: egyet magának, kettőt pedig a hallgatóinak.

Eredeti feladat

ACM ICPC 2017 Asia HCMC Vietnam National Programming Contest