Wishlist Worries

View as PDF

Submit solution


Points: 17 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

The economy has been pretty bad lately, and it's affecting the village in north pole too...

This year, Santa is afraid not everyone can get a toy on their wishlist. To check if this is the case, Santa uses a small sample of N children's wishlists and wants to know how many of them can have at least one item fulfilled in their wishlist with an optimal distribution of toys.

There are M different toys that children have put on their wishlist this year. Santa estimates that with his proportion of the sample to real-life population, he currently has enough resources to make a_i units of the i-th toy.

Each child has put C_i toys on their wishlist, each a distinct toy between 1 and M inclusive.

Santa wants to know the percent of children that can recieve a toy from their wishlist based on his sample. Can you help him?

Constraints

For all subtasks,

1 \le N, M, a_i \le 300

1 \le C_i \le M

Subtask 1 [20%]

1 \le N, M \le 10

a_i = 1

Subtask 2 [30%]

a_i = 1

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line of input will contain 2 space-separated integers N and M.

The next N lines will first contain C_i, followed by a space, followed by C_i distinct space-separated integers between 1 and M, denoting the wishlist for the i-th child.

The final line will contain M space-separated integers a_i.

Output Specification

Output a number X \ (0 \le X \le 100), the percent of children that can recieve a toy from their wishlist in this sample. Outputs with a relative or absolute error of 10^{-4} will be accepted.

Sample Input 1

3 2
2 1 2
1 1
1 1
1 2

Sample Output 1

66.6666

Explanation for Sample Output 1

All 3 children want toy 1 and only child 1 wants both toys 1 and 2. We can give child 1 toy 2, but since there is only one of toy 1, We can give either child 2 or 3 toy 1 but not both.

Thus, a maximum of \frac{2}{3} = 66.6666 \% of children can recieve a toy from their wishlist.

Sample Input 2

5 5
2 1 4
2 3 1
1 1
3 2 3 1
1 4
2 1 1 2 100

Sample Output 2

100.0000

Explanation for Sample Output 2

If we give one of toy 1 to child 3, one of toy 2 to child 4, one of toy 3 to child 2, and one of toy 4 each to child 1 and 5, everyone can recieve a toy, so 100 \% of children can get toys from their wishlist.


Comments

There are no comments at the moment.