A szegény szakács

Wolfgang Puck terjedelmes süteményrecept-gyűjteménnyel rendelkezik. A receptek külön kötetekbe vannak rendezve a sütemények típusától függően. Bár Wolfgangnak világszerte vannak éttermei, most éppen nehéz időket él, és nem nagyon tud megengedni magának bizonyos alapanyagokat a süteményeihez. Milyen sütiket tud elkészíteni a szerény költségvetéséből?

A bemenet specifikációja

A bemenet első sorában t, a kötetek száma szerepel (1 ≤ t ≤ 100). Minden kötet a kötet címével kezdődik, majd a következő sorban m-mel, n-nel és b-vel folytatódik (1 ≤ m, n ≤ 100, 1 ≤ b ≤ 10⁶), ahol b a Wolfgang rendelkezésére álló pénzösszeg dollárban. A következő m sor „alapanyag c” alakú (lásd a példa bemenetet), ahol c (0 ≤ c ≤ 5000) egy egységnyi alapanyag ára dollárban.

Ezután n recept következik. Minden recept egy név-vel kezdődik egy sorban, majd az ezt követő sor tartalmazza k-t (1 ≤ k ≤ 100). A következő k sor „hozzávaló x” alakú (lásd a példa bemenetet), ahol x azt adja meg, hogy a hozzávaló alapanyagból hány egységet kell felhasználni a név nevű recept elkészítéséhez.

A kimenet specifikációja

Minden kötet esetén a kimenetre kell írni a kötet címét csupa nagybetűvel, majd külön sorokban a Wolfgang pénzéből elkészíthető receptek nevét költség szerinti növekvő sorrendben. Ha nincs ilyen recept, a „Too expensive!” szöveget kell kiírni. Ha több receptnek is azonos a költsége, akkor azokat lexikografikus sorrendben kell felsorolni. Minden kötet után egy üres sort is a kimenetre kell írni.

Példa bemenet

1. 2
2. My Favourite Cheesecake
3. 8 3 100
4. sugar 4
5. water 0
6. lemonjuice 3
7. creamcheese 20
8. vanilla 5
9. egg 5
10. cream 10
11. strawberry 5
12. Strawberry Whipped Cream
13. 2
14. cream 5
15. strawberry 3
16. Scrumptious Caramel Topping
17. 3
18. sugar 6
19. water 3
20. lemonjuice 1
21. Secret Cheesecake Base
22. 5
23. creamcheese 3
24. sugar 5
25. vanilla 1
26. egg 6
27. cream 1
28. Million Dollar Cakes
29. 3 1 999999
30. costlyflour 500
31. gold 4500
32. diamond 5000
33. Display Cake - Do Not Eat!
34. 3
35. costlyflour 100
36. gold 100
37. diamond 100

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

A példa bemenethez tartozó kimenet

1. MY FAVOURITE CHEESECAKE
2. Scrumptious Caramel Topping
3. Strawberry Whipped Cream
5. MILLION DOLLAR CAKES
6. Too expensive!

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