Transportation Delegation

A company called Amalgamated in the country of Acmania has hired you to oversee the shipping of raw materials to its factories. Every supplier of raw materials and every factory sits in one state of Acmania. No state holds both a supplier and a factory, and no state holds two suppliers or two factories. Only the transportation companies named by law may carry raw materials across a state line. Each transportation company has a list of states it is allowed to work in, and it can carry raw materials between any two states on that list.

Competition between factories and between suppliers is fierce, so one transportation company picks up the output of at most one supplier and hands it to at most one factory. Instead of a factory it may hand the load to one other transportation company. A handoff between two companies happens only in a state where both are allowed to work. One supplier contracts with only one factory, and one factory contracts with only one supplier.

Determine the largest number of factories that can be supplied with raw materials.

For example, suppose suppliers sit in states A, B and C, and factories sit in states D, E and F. You contract three transportation firms: firm 1 can work in states A, E and G, firm 2 can work in states A, C and E, and firm 3 can work in states B, D and F. At most two factories can be supplied. For instance, the factory in E is supplied from the supplier in A using firm 1, and the factory in F is supplied from the supplier in B using firm 3. Add a fourth firm that works in states G and F, and all three factories can be supplied: the factory in D from B using firm 3, the factory in E from C using firm 2, and the factory in F from A using firm 1 followed by firm 4.

The first line holds the positive integers $s$, $r$, $f$ and $t$: the number of states, the number of raw material sites, the number of factories and the number of transportation companies. ($1 \le r, f \le 200$, $r + f \le s \le 600$, $1 \le t \le 1000$)

The second line holds $r$ state names, one for each raw material site.

The third line holds $f$ state names, one for each factory.

The next $t$ lines describe one transportation company each. Each of those lines starts with the number of states the company is allowed to work in, $n$ ($1 \le n \le s$), followed by $n$ state names.

No state holds both a raw material site and a factory. Every state name is an alphabetic string with no blanks.

Print the largest number of factories that can be supplied with raw materials.