PBCGAME - PBCGAME

The company "PBC" has made a game which consists of small platforms and pipes. There are 3 types of platforms: starting platforms (there are N1 of them), finishing platforms (there are N3 of them) and middle platforms (there are N2 of them). All starting platforms stand at identical height. Finishing platforms stand also at identical height. All heights of middle platforms are various. They have less height than starting, but greater height than finishing platforms. Each platform has an unique number from 1 up to N1+N2+N3. First N1 numbers are starting platforms, next N2 numbers are middle platforms, and the last N3 numbers are finishing platforms. All middle platforms are numbered in order of decrease of height. It means that if number of middle platform A is less than number of platform B, than height of A is greater than height of B.

There is a ball on each of starting platforms. The ball can move from platform A to platform B if they are connected by a pipe, and height A is greater than height B. Each finishing platform can hold only one ball. If there is a ball on a platform the player can choose a direction of the further way of the ball, it means that he can choose a platform, where the ball will go. Also given a number C for each middle platform which means a maximum quantity of balls which can pass it during the game. The goal of the game is to drive the greatest possible number of ball to the finishing platforms.

You need to find out what maximum quantity of balls can appear on finishing platforms at the end of the game.

Input

The input file has the following order:
N1 N2 N3
CN1+1
...
CN1+N2
K1 A[1,1] ... A[1,K1]
K2 A[2,1] ... A[2,K2]
...
KN1+N2 A[N1+N2,1] ... A[N1+N2,KN1+N2]

Where N1, N2, N3 are the amounts of starting, middle and finishing platforms. Cj is the maximum amount of balls, which can pass the middle platform with the number j (N1+1 <= j <= N1+N2) during the game. Ki is the number of pipes, connected with the platform i (1 <= i <= N1+N2). The elements of the array A, are the numbers of platforms where the ball can move from the appropriate platform (platforms with numbers i and A[i] are connected with a pipe).

Output

The output file must contain a number, which means the max amount of balls, which can appear at the finishing platforms at the end of the game.

Example

Input:
3 4 3
3
2
1
2
1 4
1 4
1 4
2 5 6
1 7
1 7
3 8 9 10

Output:
2
Limitations:
  • All the numbers are integer.
  • 0 < N1, N3 < 51
  • 1 < N1+N2+N3 < 201
  • 0 <= Cj <= 50
  • There are no pipes between starting platforms.
  • There are no pipes between finishing platforms.

Added by:Phan Công Minh
Date:2010-02-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:A.N. Danchenko - belarus

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.