Problem B

BANKRUPT BAKER

Wolfgang Puck has an extensive collection of cake recipes. They are separated into different binders depending on the type of cake. Although Wolfgang has restaurant franchises all over the world, he is in a period of hard times and is struggling to afford ingredients for his cakes. What cakes can he create with his small budget?

Input

On the first line you are given t (1 ≤ t ≤ 100), the number of binders. Each binder begins with title, the name of the binder, then on the next line m n b (1 ≤ m, n ≤ 100, 1 ≤ b ≤ 10⁶) where b is Wolfgang's budget in dollars. The next m lines are given as "ingredient c" (see sample input) where c (0 ≤ c ≤ 5000) is the price in dollars for one unit of ingredient.

Then follow n recipes. Each recipe begins with name on a line of its own, then on the very next line k (1 ≤ k ≤ 100). The following k lines are of the form "requirement x" (see sample input) where x is the number of units of the ingredient requirement used in the recipe name.

Output

For each binder, output the name of the binder in uppercase letters then on separate lines a list of recipes within Wolfgang's budget in increasing order of cost. If no such recipe exists, print "Too expensive!". If recipes have the same cost print them in lexicographical order. Print a blank line after each binder.

Sample Input

2
My Favourite Cheesecake
8 3 100
sugar 4
water 0
lemonjuice 3
creamcheese 20
vanilla 5
egg 5
cream 10
strawberry 5
Strawberry Whipped Cream
2
cream 5
strawberry 3
Scrumptious Caramel Topping
3
sugar 6
water 3
lemonjuice 1
Secret Cheesecake Base
5
creamcheese 3
sugar 5
vanilla 1
egg 6
cream 1
Million Dollar Cakes
3 1 999999
costlyflour 500
gold 4500
diamond 5000
Display Cake - Do Not Eat!
3
costlyflour 100
gold 100
diamond 100

Output for the Sample Input

MY FAVOURITE CHEESECAKE
Scrumptious Caramel Topping
Strawberry Whipped Cream

MILLION DOLLAR CAKES
Too expensive!

---

Sean McIntyre
Calgary Collegiate Programming Contest 2007

題目描述：
給一個食譜書的名稱, 裡面有一些蛋糕的食譜, 而手上有一些預算, 同時給你每個材料的單價,
接著告訴你每個蛋糕分別的材料量, 請輸出可以做出來的蛋糕, 輸出的時候按照價錢低到高,
相同的時候按照蛋糕名稱的字典順序輸出。

食譜書的名稱一律轉成大寫。

#include <stdio.h>
#include <set>
#include <map>
#include <iostream>
using namespace std;
struct E {
    string name;
    int cost;
    bool operator<(const E & a) const {
        if(cost != a.cost)
            return cost < a.cost;
        return name.compare(a.name) < 0;
    }
};
int main() {
    int testcase;
    char name[105], foo[105], name2[105];
    scanf("%d", &testcase);
    while(getchar() != '\n');
    while(testcase--) {
        gets(name);
        int i;
        for(i = 0; name[i]; i++)
            if(name[i] >= 'a' && name[i] <= 'z')
                name[i] -= 32;
        puts(name);
        gets(foo);
        int n, m, cost, x, q;
        map<string, int> R;
        set<E> ret;
        E tmp;
        sscanf(foo, "%d %d %d", &n, &m, &cost);
        while(n--) {
            gets(foo);
            sscanf(foo, "%s %d", name, &x);
            R[name] = x;
        }
        while(m--) {
            gets(name);
            gets(foo);
            sscanf(foo, "%d", &q);
            int cc = 0;
            while(q--) {
                gets(foo);
                sscanf(foo, "%s %d", name2, &x);
                cc += R[name2]*x;
            }
            if(cc <= cost) {
                tmp.name = name;
                tmp.cost = cc;
                ret.insert(tmp);
            }
        }
        for(set<E>::iterator it = ret.begin();
            it != ret.end(); it++) {
            cout << it->name << endl;
        }
        if(ret.size() == 0)
            puts("Too expensive!");
        puts("");
    }
    return 0;
}