Laundry

Interview

Time limit1sMemory limit1024 MB

Summary

Given colors partitioned into washable groups and counts of clothes per color, find how many machine loads of capacity M are needed.

Level: Easy3 of 10
Topics: Math, Implementation, Greedy, Array
Solved: No attempts yet

Problem

Tomas does not like doing laundry, even though he owns a washing machine. Sometimes, when Tomas decides to wash his clothes, he has so many that they do not all fit in the machine at once, and he has to run the machine several times in a row.

Tomas also knows that only clothes of certain colors may be washed together. We say that colors which may be washed together belong to the same clothing group. Every color belongs to exactly one clothing group.

The washing machine can hold at most $M$ items of clothing at a time. Given which colors of clothing may be washed together, help Tomas count how many washes he must run to clean all of his clothes.

Input

The first line contains three integers $N$ , $K$ , and $M$ : the number of clothing colors, the number of distinct clothing groups, and the capacity of the washing machine.

Each of the next $K$ lines contains an integer $G_i$ followed by $G_i$ integers. $G_i$ is the number of clothing colors in the $i$ -th group, and the following $G_i$ integers are the colors that belong to that group.

The next line contains $N$ integers $D_i$ , where $D_i$ is the number of clothes of color $i$ that Tomas owns.

Clothing colors are denoted by the integers from $1$ to $N$ .

Output

Output a single integer — the number of washes Tomas must run.

Constraints

$1 \le K \le N \le 1000$
$1 \le M \le 1000000$
$0 \le D_i \le 1000$

Examples2

Example 1

Input

7 3 3
3 1 2 6
1 4
3 3 5 7
3 3 0 2 4 1 2

Expected output

Example 2

Input

7 4 5
2 1 7
2 2 6
2 3 5
1 4
1 2 4 5 4 7 8

Expected output