
67  ZOJ Monthly, June 2008  1003
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 Sample Output
19 Author: WANG, Naiyan 