Welcome to ZOJ
 Contests Information Problems Runs Statistics Ranklist Clarification
67 - ZOJ Monthly, June 2008 - 1003
Decorate

Time Limit: 5 Seconds      Memory Limit: 32768 KB

Vitta likes making up, she has m decorations, but she can only wear n of them exactly. However, she marks every decoration a mark. but when some of them put on together, Vitta may be more beautiful, so Vitta decide they must be worn together. while if some others are put on together, it will make the opposite effect, so Vitta decide they can't be worn together. Today she wants to meet her lover^_^, of course she wants to be the most beautiful. Can you help her?

Input

The first line contains 4 integers m, n, s, t. The integer s represents the number of requriements that decorations must be worn together, and the integer t represents the number of requriements that decorations can't be worn together.

The next line contains m integers, represents the mark of each decoration in order.

The following s lines, the first number of each line is k, which means the number of decorations of this requriement. They must be worn together.

The following s lines, the first number of each line is p, which means the number of decorations of this requriement. They can't be worn together.

Output

Only one line, output the maximum mark Vitta can get.

Sample Input

5 3 1 1
10 6 7 1 3
2 1 2
2 1 3

Sample Output

19

Author: WANG, Naiyan

Submit    Status