Maximizing Subtask Score with Duplicate Answers

Unfortunately, you have encountered an irresponsible problem setter. In this problem, there are a total of (N) test points and (k) subtasks. The (i)-th subtask consists of (p_i) test points with indices (w_{i,1}, w_{i,2}, \dots, w_{i,p_i}). Note that a test point may belong to multiple subtasks. (\vspace{2mm})

A subtask has a score and can only be awarded that score if and only if all its test points are answered correctly. The overall score of a submission is the sum of the scores of all subtasks that are completely correct. In this problem the correct answer for test point (i) is (A_i), and the submission outputs only a single number.

Because the setter was careless, the answers (A_i) contain many duplicates, giving a chance for brute‐force attack. Now that you somehow obtained all the data, your task is to determine: which number should you output so that you obtain the highest possible total score? Also, what is that highest score? If there are multiple answers, you may output any one of them.

Formally, for each subtask, if all test points in that subtask have the same answer (v), then outputting (v) will secure that subtask's score. Your goal is to choose an integer (X) such that the sum of scores for all subtasks where all (A_{w_{i,j}} = X) is maximized.

inputFormat

The first line contains two integers (N) and (k) separated by a space. (\vspace{2mm})

The second line contains (N) integers (A_1, A_2, \dots, A_N), representing the correct answer for each test point. (\vspace{2mm})

Then (k) lines follow, each describing a subtask. Each of these lines begins with two integers: the score (s) of the subtask and the number (p) of test points in the subtask, followed by (p) integers (w_{i,1}, w_{i,2}, \dots, w_{i,p}) (1-indexed) representing the indices of the test points belonging to the subtask.

outputFormat

Output a single line with two integers separated by a space: the number (X) you should output and the maximum total score you can obtain by outputting (X).

sample

5 3
1 2 1 1 3
10 3 1 3 4
5 2 2 5
7 1 2

1 10