Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Kitchen Combinatorics

Limits 1s, 512 MB

The world-renowned Swedish Chef is planning a gourmet three-course dinner for some muppets: a starter course, a main course, and a dessert. His famous Swedish cook-book offers a wide variety of choices for each of these three courses, though some of them do not go well together (for instance, you of course cannot serve chocolate moose and sooted shreemp at the same dinner).

Each potential dish has a list of ingredients. Each ingredient is in turn available from a few different brands. Each brand is of course unique in its own special way, so using a particular brand of an ingredient will always result in a completely different dinner experience than using another brand of the same ingredient.

Some common ingredients such as pølårber may appear in two of the three chosen dishes, or in all three of them. When an ingredient is used in more than one of the three selected dishes, Swedish Chef will use the same brand of the ingredient in all of them

While waiting for the meecaroo, Swedish Chef starts wondering: how many different dinner experiences are there that he could make, by different choices of dishes and brands for the ingredients?

Input

The input consists of:

  • one line containing five integers r (1 ≤ r ≤ 1000), s, m, d (1 ≤ s, m, d ≤ 25), n (0 ≤ n ≤ 2000), where r is the number of different ingredients that exist, m, s, d are the number of available starter dishes, main dishes, and desserts, respectively, and n is the number of pairs of dishes that do not go well together.

  • one line containing r integers b1,…, br (1 ≤ bi ≤ 100), where bi is the number of different brands of ingredient i.

  • s+m+d lines describing the s starter dishes, then the m main dishes, then the d desserts. Each such line starts with an integer k (1 ≤ k ≤ 20) denoting the number of ingredients of the dish, and is followed by k distinct integers i1,…, ik, where for each j (1 ≤ j ≤ k), ij (1 ≤ i j ≤ r) is an ingredient.

  • n lines each containing two incompatible dishes. Each dish is identified by an integer j (1 ≤ j ≤ s+m+d), referring to the j-th dish given in the input (so 1 ≤ j ≤ s refers to the starter dishes, s < j ≤ s+m refers to the main dishes, and s+m < j ≤ s+m+d refers to the desserts).

Each pair of incompatible dishes in the input consists of two dishes of different types, and any one pair of dishes is listed at most once.

Output

If the number of different dinner experiences Swedish Chef can make is at most 1018, then output that number. Otherwise, output “too many”.

Samples

InputOutput
6 1 1 1 0
2 3 1 5 3 2
2 1 2
3 3 4 5
1 6
180
InputOutput
3 2 2 1 1
2 3 2
1 1
1 2
1 2
1 3
1 1
2 3
22
InputOutput
3 1 1 1 1
5 5 5
3 1 2 3
3 1 2 3
3 1 2 3
2 1
0
InputOutput
10 1 1 1 0
100 100 100 100 100 100 100 100 100 100
4 1 2 3 4
3 5 6 7
3 8 9 10
too many

This NWERC 2015 problem is licensed under the CC BY-SA 3.0 license.

You can find the original problem on the NWERC website.


    Discussion
    Statistics

    100% Solution Ratio

    emrul_muEarliest, 2M ago

    emrul_muFastest, 0.1s

    emrul_muLightest, 262 kB

    emrul_muShortest, 1637B

    Submit

    Login to submit